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 <= 105word1andword2consist 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$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}