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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def isItPossible(self, word1: str, word2: str) -> bool:
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in word1:
cnt1[ord(c) - ord('a')] += 1
for c in word2:
cnt2[ord(c) - ord('a')] += 1
for i, a in enumerate(cnt1):
for j, b in enumerate(cnt2):
if a and b:
cnt1[i], cnt2[j] = cnt1[i] - 1, cnt2[j] - 1
cnt1[j], cnt2[i] = cnt1[j] + 1, cnt2[i] + 1
if sum(v > 0 for v in cnt1) == sum(v > 0 for v in cnt2):
return True
cnt1[i], cnt2[j] = cnt1[i] + 1, cnt2[j] + 1
cnt1[j], cnt2[i] = cnt1[j] - 1, cnt2[i] - 1
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public boolean isItPossible(String word1, String word2) {
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < word1.length(); ++i) {
++cnt1[word1.charAt(i) - 'a'];
}
for (int i = 0; i < word2.length(); ++i) {
++cnt2[word2.charAt(i) - 'a'];
}
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (cnt1[i] > 0 && cnt2[j] > 0) {
--cnt1[i];
--cnt2[j];
++cnt1[j];
++cnt2[i];
int d = 0;
for (int k = 0; k < 26; ++k) {
if (cnt1[k] > 0) {
++d;
}
if (cnt2[k] > 0) {
--d;
}
}
if (d == 0) {
return true;
}
++cnt1[i];
++cnt2[j];
--cnt1[j];
--cnt2[i];
}
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
bool isItPossible(string word1, string word2) {
int cnt1[26]{};
int cnt2[26]{};
for (char& c : word1) {
++cnt1[c - 'a'];
}
for (char& c : word2) {
++cnt2[c - 'a'];
}
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (cnt1[i] > 0 && cnt2[j] > 0) {
--cnt1[i];
--cnt2[j];
++cnt1[j];
++cnt2[i];
int d = 0;
for (int k = 0; k < 26; ++k) {
if (cnt1[k] > 0) {
++d;
}
if (cnt2[k] > 0) {
--d;
}
}
if (d == 0) {
return true;
}
++cnt1[i];
++cnt2[j];
--cnt1[j];
--cnt2[i];
}
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| func isItPossible(word1 string, word2 string) bool {
cnt1 := [26]int{}
cnt2 := [26]int{}
for _, c := range word1 {
cnt1[c-'a']++
}
for _, c := range word2 {
cnt2[c-'a']++
}
for i := range cnt1 {
for j := range cnt2 {
if cnt1[i] > 0 && cnt2[j] > 0 {
cnt1[i], cnt2[j] = cnt1[i]-1, cnt2[j]-1
cnt1[j], cnt2[i] = cnt1[j]+1, cnt2[i]+1
d := 0
for k, a := range cnt1 {
if a > 0 {
d++
}
if cnt2[k] > 0 {
d--
}
}
if d == 0 {
return true
}
cnt1[i], cnt2[j] = cnt1[i]+1, cnt2[j]+1
cnt1[j], cnt2[i] = cnt1[j]-1, cnt2[i]-1
}
}
}
return false
}
|
