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 <= 105word1 and word2 consist of only lowercase English letters.
Solutions
Solution 1: Counting + Enumeration
We first use two arrays cnt1 and cnt2 of length 26 to record the frequency of each character in the strings word1 and word2, respectively.
Then, we count the number of distinct characters in word1 and word2, denoted as x and y respectively.
Next, we enumerate each character c1 in word1 and each character c2 in word2. If c1 = c2, we only need to check if x and y are equal; otherwise, we need to check if x - (cnt1[c1] = 1) + (cnt1[c2] = 0) and y - (cnt2[c2] = 1) + (cnt2[c1] = 0) are equal. If they are equal, then we have found a solution and return true.
If we have enumerated all characters and have not found a suitable solution, we return false.
The time complexity is O(m + n + |Σ|^2), where m and n are the lengths of the strings word1 and word2, and Σ is the character set. In this problem, the character set consists of lowercase letters, so |Σ| = 26.
PythonJavaC++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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
