2531. Make Number of Distinct Characters Equal

Description

You are given two 0-indexed strings word1 and word2.

A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].

Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.

 

Example 1:

Input: word1 = "ac", word2 = "b"
Output: false
Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.

Example 2:

Input: word1 = "abcc", word2 = "aab"
Output: true
Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.

Example 3:

Input: word1 = "abcde", word2 = "fghij"
Output: true
Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.

 

Constraints:

• 1 <= word1.length, word2.length <= 105
• word1 and word2 consist of only lowercase English letters.

Solutions

Solution 1: Counting + Enumeration

We first use two arrays \(\textit{cnt1}\) and \(\textit{cnt2}\) of length \(26\) to record the frequency of each character in the strings \(\textit{word1}\) and \(\textit{word2}\), respectively.

Then, we count the number of distinct characters in \(\textit{word1}\) and \(\textit{word2}\), denoted as \(x\) and \(y\) respectively.

Next, we enumerate each character \(c1\) in \(\textit{word1}\) and each character \(c2\) in \(\textit{word2}\). If \(c1 = c2\), we only need to check if \(x\) and \(y\) are equal; otherwise, we need to check if \(x - (\textit{cnt1}[c1] = 1) + (\textit{cnt1}[c2] = 0)\) and \(y - (\textit{cnt2}[c2] = 1) + (\textit{cnt2}[c1] = 0)\) are equal. If they are equal, then we have found a solution and return \(\text{true}\).

If we have enumerated all characters and have not found a suitable solution, we return \(\text{false}\).

The time complexity is \(O(m + n + |\Sigma|^2)\), where \(m\) and \(n\) are the lengths of the strings \(\textit{word1}\) and \(\textit{word2}\), and \(\Sigma\) is the character set. In this problem, the character set consists of lowercase letters, so \(|\Sigma| = 26\).

Python3JavaC++GoTypeScript

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        cnt1 = Counter(word1)
        cnt2 = Counter(word2)
        x, y = len(cnt1), len(cnt2)
        for c1, v1 in cnt1.items():
            for c2, v2 in cnt2.items():
                if c1 == c2:
                    if x == y:
                        return True
                else:
                    a = x - (v1 == 1) + (cnt1[c2] == 0)
                    b = y - (v2 == 1) + (cnt2[c1] == 0)
                    if a == b:
                        return True
        return False

class Solution {
    public boolean isItPossible(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        int x = 0, y = 0;
        for (int i = 0; i < word1.length(); ++i) {
            if (++cnt1[word1.charAt(i) - 'a'] == 1) {
                ++x;
            }
        }
        for (int i = 0; i < word2.length(); ++i) {
            if (++cnt2[word2.charAt(i) - 'a'] == 1) {
                ++y;
            }
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (cnt1[i] > 0 && cnt2[j] > 0) {
                    if (i == j) {
                        if (x == y) {
                            return true;
                        }
                    } else {
                        int a = x - (cnt1[i] == 1 ? 1 : 0) + (cnt1[j] == 0 ? 1 : 0);
                        int b = y - (cnt2[j] == 1 ? 1 : 0) + (cnt2[i] == 0 ? 1 : 0);
                        if (a == b) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

class Solution {
public:
    bool isItPossible(string word1, string word2) {
        int cnt1[26]{};
        int cnt2[26]{};
        int x = 0, y = 0;
        for (char& c : word1) {
            if (++cnt1[c - 'a'] == 1) {
                ++x;
            }
        }
        for (char& c : word2) {
            if (++cnt2[c - 'a'] == 1) {
                ++y;
            }
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (cnt1[i] > 0 && cnt2[j] > 0) {
                    if (i == j) {
                        if (x == y) {
                            return true;
                        }
                    } else {
                        int a = x - (cnt1[i] == 1 ? 1 : 0) + (cnt1[j] == 0 ? 1 : 0);
                        int b = y - (cnt2[j] == 1 ? 1 : 0) + (cnt2[i] == 0 ? 1 : 0);
                        if (a == b) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
};

func isItPossible(word1 string, word2 string) bool {
    cnt1 := [26]int{}
    cnt2 := [26]int{}
    x, y := 0, 0
    for _, c := range word1 {
        cnt1[c-'a']++
        if cnt1[c-'a'] == 1 {
            x++
        }
    }
    for _, c := range word2 {
        cnt2[c-'a']++
        if cnt2[c-'a'] == 1 {
            y++
        }
    }
    for i := range cnt1 {
        for j := range cnt2 {
            if cnt1[i] > 0 && cnt2[j] > 0 {
                if i == j {
                    if x == y {
                        return true
                    }
                } else {
                    a := x
                    if cnt1[i] == 1 {
                        a--
                    }
                    if cnt1[j] == 0 {
                        a++
                    }

                    b := y
                    if cnt2[j] == 1 {
                        b--
                    }
                    if cnt2[i] == 0 {
                        b++
                    }

                    if a == b {
                        return true
                    }
                }
            }
        }
    }
    return false
}

function isItPossible(word1: string, word2: string): boolean {
    const cnt1: number[] = Array(26).fill(0);
    const cnt2: number[] = Array(26).fill(0);
    let [x, y] = [0, 0];

    for (const c of word1) {
        if (++cnt1[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
            ++x;
        }
    }

    for (const c of word2) {
        if (++cnt2[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
            ++y;
        }
    }

    for (let i = 0; i < 26; ++i) {
        for (let j = 0; j < 26; ++j) {
            if (cnt1[i] > 0 && cnt2[j] > 0) {
                if (i === j) {
                    if (x === y) {
                        return true;
                    }
                } else {
                    const a = x - (cnt1[i] === 1 ? 1 : 0) + (cnt1[j] === 0 ? 1 : 0);
                    const b = y - (cnt2[j] === 1 ? 1 : 0) + (cnt2[i] === 0 ? 1 : 0);
                    if (a === b) {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

Comments