Problem

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 withexactly one move. _Return false otherwise.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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 <= 10^5
  • word1 and word2 consist of only lowercase English letters.

Solution

Method 1 – Brute Force with Frequency Counting

Intuition

We want to check if swapping any character between the two words can make the number of distinct characters in both words equal. By trying all possible swaps and counting distinct characters after each, we can determine if it’s possible.

Approach

  1. For each character in word1, and each character in word2, try swapping them.
  2. After the swap, count the number of distinct characters in both words.
  3. If the counts are equal, return true.
  4. If no swap leads to equal distinct counts, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool isItPossible(string word1, string word2) {
        for (char c1 = 'a'; c1 <= 'z'; ++c1) {
            for (char c2 = 'a'; c2 <= 'z'; ++c2) {
                int cnt1[26] = {}, cnt2[26] = {};
                for (char ch : word1) cnt1[ch-'a']++;
                for (char ch : word2) cnt2[ch-'a']++;
                if (!cnt1[c1-'a'] || !cnt2[c2-'a']) continue;
                cnt1[c1-'a']--, cnt1[c2-'a']++;
                cnt2[c2-'a']--, cnt2[c1-'a']++;
                int d1 = 0, d2 = 0;
                for (int i = 0; i < 26; ++i) d1 += cnt1[i] > 0, d2 += cnt2[i] > 0;
                if (d1 == d2) return true;
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isItPossible(word1, word2 string) bool {
    for c1 := 'a'; c1 <= 'z'; c1++ {
        for c2 := 'a'; c2 <= 'z'; c2++ {
            cnt1 := make([]int, 26)
            cnt2 := make([]int, 26)
            for _, ch := range word1 { cnt1[ch-'a']++ }
            for _, ch := range word2 { cnt2[ch-'a']++ }
            if cnt1[c1-'a'] == 0 || cnt2[c2-'a'] == 0 { continue }
            cnt1[c1-'a']--
            cnt1[c2-'a']++
            cnt2[c2-'a']--
            cnt2[c1-'a']++
            d1, d2 := 0, 0
            for i := 0; i < 26; i++ {
                if cnt1[i] > 0 { d1++ }
                if cnt2[i] > 0 { d2++ }
            }
            if d1 == d2 { return true }
        }
    }
    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

class Solution {
    public boolean isItPossible(String word1, String word2) {
        for (char c1 = 'a'; c1 <= 'z'; ++c1) {
            for (char c2 = 'a'; c2 <= 'z'; ++c2) {
                int[] cnt1 = new int[26], cnt2 = new int[26];
                for (char ch : word1.toCharArray()) cnt1[ch-'a']++;
                for (char ch : word2.toCharArray()) cnt2[ch-'a']++;
                if (cnt1[c1-'a'] == 0 || cnt2[c2-'a'] == 0) continue;
                cnt1[c1-'a']--;
                cnt1[c2-'a']++;
                cnt2[c2-'a']--;
                cnt2[c1-'a']++;
                int d1 = 0, d2 = 0;
                for (int i = 0; i < 26; ++i) {
                    if (cnt1[i] > 0) d1++;
                    if (cnt2[i] > 0) d2++;
                }
                if (d1 == d2) return true;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun isItPossible(word1: String, word2: String): Boolean {
        for (c1 in 'a'..'z') {
            for (c2 in 'a'..'z') {
                val cnt1 = IntArray(26)
                val cnt2 = IntArray(26)
                for (ch in word1) cnt1[ch-'a']++
                for (ch in word2) cnt2[ch-'a']++
                if (cnt1[c1-'a'] == 0 || cnt2[c2-'a'] == 0) continue
                cnt1[c1-'a']--
                cnt1[c2-'a']++
                cnt2[c2-'a']--
                cnt2[c1-'a']++
                val d1 = cnt1.count { it > 0 }
                val d2 = cnt2.count { it > 0 }
                if (d1 == d2) return true
            }
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        for c1 in set(word1):
            for c2 in set(word2):
                a = list(word1)
                b = list(word2)
                a[a.index(c1)] = c2
                b[b.index(c2)] = c1
                if len(set(a)) == len(set(b)):
                    return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn is_it_possible(word1: String, word2: String) -> bool {
        for c1 in b'a'..=b'z' {
            for c2 in b'a'..=b'z' {
                let mut cnt1 = [0; 26];
                let mut cnt2 = [0; 26];
                for &ch in word1.as_bytes() { cnt1[(ch-b'a') as usize] += 1; }
                for &ch in word2.as_bytes() { cnt2[(ch-b'a') as usize] += 1; }
                if cnt1[(c1-b'a') as usize] == 0 || cnt2[(c2-b'a') as usize] == 0 { continue; }
                cnt1[(c1-b'a') as usize] -= 1;
                cnt1[(c2-b'a') as usize] += 1;
                cnt2[(c2-b'a') as usize] -= 1;
                cnt2[(c1-b'a') as usize] += 1;
                let d1 = cnt1.iter().filter(|&&x| x > 0).count();
                let d2 = cnt2.iter().filter(|&&x| x > 0).count();
                if d1 == d2 { return true; }
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    isItPossible(word1: string, word2: string): boolean {
        for (let c1 = 97; c1 <= 122; ++c1) {
            for (let c2 = 97; c2 <= 122; ++c2) {
                const cnt1 = Array(26).fill(0), cnt2 = Array(26).fill(0);
                for (const ch of word1) cnt1[ch.charCodeAt(0)-97]++;
                for (const ch of word2) cnt2[ch.charCodeAt(0)-97]++;
                if (!cnt1[c1-97] || !cnt2[c2-97]) continue;
                cnt1[c1-97]--;
                cnt1[c2-97]++;
                cnt2[c2-97]--;
                cnt2[c1-97]++;
                const d1 = cnt1.filter(x => x > 0).length;
                const d2 = cnt2.filter(x => x > 0).length;
                if (d1 === d2) return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(26^2 * (n + m)), where n and m are the lengths of the words, as we try all character swaps.
  • 🧺 Space complexity: O(1), as we use only fixed-size arrays for counting.