2531. Make Number of Distinct Characters Equal

MediumHash TableStringCounting

Problem Description

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

A move operation allows you to:

Choose any index i from word1 (where 0 <= i < word1.length)
Choose any index j from word2 (where 0 <= j < word2.length)
Swap the character at word1[i] with the character at word2[j]

Your goal is to determine if it's possible to make both strings have the same number of distinct characters by performing exactly one move.

For example:

If word1 has 3 distinct characters and word2 has 5 distinct characters before the swap
After one swap, both strings should have the same number of distinct characters (like both having 4 distinct characters)

The function should return true if such a swap exists, and false otherwise.

The key insight is that when you swap characters between the two strings:

A character might be added to or removed from each string's set of distinct characters
If you swap word1[i] with word2[j]:
- word1 loses one occurrence of word1[i] and gains one occurrence of word2[j]
- word2 loses one occurrence of word2[j] and gains one occurrence of word1[i]
- This might change the count of distinct characters in each string depending on whether these were the only occurrences of those characters

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we need to think about what happens when we swap two characters between the strings.

First, let's understand what changes when we swap word1[i] (containing character c1) with word2[j] (containing character c2):

When c1 == c2 (swapping same characters):
- We're essentially swapping identical characters
- The distinct character count in both strings remains unchanged
- This only makes sense if both strings already have equal distinct counts
When c1 != c2 (swapping different characters):
- word1 loses one occurrence of c1 and gains one occurrence of c2
- word2 loses one occurrence of c2 and gains one occurrence of c1
The distinct count changes depend on:
- Does word1 lose a distinct character? (Yes, if c1 appears only once in word1)
- Does word1 gain a distinct character? (Yes, if c2 doesn't exist in word1 before the swap)
- Does word2 lose a distinct character? (Yes, if c2 appears only once in word2)
- Does word2 gain a distinct character? (Yes, if c1 doesn't exist in word2 before the swap)

Since we need to check if exactly one swap can equalize the distinct counts, we can try all possible swaps. For each pair of characters (c1, c2) where c1 comes from word1 and c2 comes from word2, we calculate what the new distinct counts would be after the swap.

The key formula for the new distinct count after swapping different characters:

New distinct count for word1: x - (cnt1[c1] == 1) + (cnt1[c2] == 0)
New distinct count for word2: y - (cnt2[c2] == 1) + (cnt2[c1] == 0)

Where x and y are the original distinct counts, and the boolean expressions evaluate to 1 if true, 0 if false.

By checking all possible character pairs, we can determine if any swap results in equal distinct counts.

Solution Approach

The implementation follows a systematic approach using counting and enumeration:

Step 1: Count Character Frequencies

We use Python's Counter to create frequency maps for both strings:

cnt1 = Counter(word1) - stores frequency of each character in word1
cnt2 = Counter(word2) - stores frequency of each character in word2

Step 2: Calculate Initial Distinct Counts

We determine the number of distinct characters in each string:

x = len(cnt1) - number of distinct characters in word1
y = len(cnt2) - number of distinct characters in word2

Step 3: Enumerate All Possible Swaps

We iterate through every possible pair of characters:

for c1, v1 in cnt1.items():
    for c2, v2 in cnt2.items():

Here, c1 is a character from word1 with frequency v1, and c2 is a character from word2 with frequency v2.

Step 4: Handle Two Cases

For each pair (c1, c2), we check two scenarios:

Case 1: Same Characters (c1 == c2)

Swapping identical characters doesn't change distinct counts
Simply check if x == y (already equal)
If true, return True

Case 2: Different Characters (c1 != c2)

Calculate new distinct count for word1 after swap:
- a = x - (v1 == 1) + (cnt1[c2] == 0)
- Subtract 1 if c1 appears only once (will disappear after swap)
- Add 1 if c2 doesn't exist in word1 (will be introduced)
Calculate new distinct count for word2 after swap:
- b = y - (v2 == 1) + (cnt2[c1] == 0)
- Subtract 1 if c2 appears only once (will disappear after swap)
- Add 1 if c1 doesn't exist in word2 (will be introduced)
If a == b, we found a valid swap, return True

Step 5: Return False if No Valid Swap Found

If we've checked all possible character pairs and none result in equal distinct counts, return False.

The time complexity is O(n + m + 26²) where n and m are the lengths of the strings, and space complexity is O(26) for the frequency counters.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: word1 = "abcc", word2 = "aab"

Step 1: Count Character Frequencies

cnt1 = {'a': 1, 'b': 1, 'c': 2}
cnt2 = {'a': 2, 'b': 1}

Step 2: Calculate Initial Distinct Counts

x = len(cnt1) = 3 (word1 has 3 distinct characters: a, b, c)
y = len(cnt2) = 2 (word2 has 2 distinct characters: a, b)

Step 3-4: Enumerate All Possible Swaps

Let's check each possible character pair:

Pair ('a', 'a'): Swapping same characters

Since c1 == c2, distinct counts remain unchanged
Check if x == y? No (3 ≠ 2), continue

Pair ('a', 'b'): Different characters

word1 after swap: loses 'a' (only 1 occurrence), gains 'b'
- a = 3 - 1 + 0 = 2 (lost 'a', but 'b' already exists)
word2 after swap: loses 'b' (only 1 occurrence), gains 'a'
- b = 2 - 1 + 0 = 1 (lost 'b', but 'a' already exists)
Check if a == b? No (2 ≠ 1), continue

Pair ('b', 'a'): Different characters

word1 after swap: loses 'b' (only 1 occurrence), gains 'a'
- a = 3 - 1 + 0 = 2 (lost 'b', but 'a' already exists)
word2 after swap: keeps 'a' (has 2 occurrences), gains 'b'
- b = 2 - 0 + 0 = 2 ('a' still present, 'b' already exists)
Check if a == b? Yes (2 == 2), return True

We found a valid swap! Swapping the 'b' in word1 with an 'a' in word2 gives us:

word1: "aacc" → 2 distinct characters (a, c)
word2: "bab" → 2 distinct characters (a, b)

Both strings now have exactly 2 distinct characters, so the function returns True.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def isItPossible(self, word1: str, word2: str) -> bool:
5        # Count frequency of each character in both words
6        char_count_1 = Counter(word1)
7        char_count_2 = Counter(word2)
8      
9        # Get the number of distinct characters in each word
10        distinct_count_1 = len(char_count_1)
11        distinct_count_2 = len(char_count_2)
12      
13        # Try every possible swap: character from word1 with character from word2
14        for char_1, freq_1 in char_count_1.items():
15            for char_2, freq_2 in char_count_2.items():
16              
17                # Case 1: Swapping the same character (no actual change in character types)
18                if char_1 == char_2:
19                    # If distinct counts are already equal, this swap works
20                    if distinct_count_1 == distinct_count_2:
21                        return True
22              
23                # Case 2: Swapping different characters
24                else:
25                    # Calculate new distinct count for word1 after swap:
26                    # - Lose char_1 (subtract 1 if it only appears once)
27                    # - Gain char_2 (add 1 if it doesn't exist in word1)
28                    new_distinct_1 = distinct_count_1 - (freq_1 == 1) + (char_count_1[char_2] == 0)
29                  
30                    # Calculate new distinct count for word2 after swap:
31                    # - Lose char_2 (subtract 1 if it only appears once)
32                    # - Gain char_1 (add 1 if it doesn't exist in word2)
33                    new_distinct_2 = distinct_count_2 - (freq_2 == 1) + (char_count_2[char_1] == 0)
34                  
35                    # Check if the swap results in equal distinct counts
36                    if new_distinct_1 == new_distinct_2:
37                        return True
38      
39        # No valid swap found
40        return False
41

1class Solution {
2    public boolean isItPossible(String word1, String word2) {
3        // Count frequency of each character in both strings
4        int[] charFrequency1 = new int[26];
5        int[] charFrequency2 = new int[26];
6      
7        // Count distinct characters in each string
8        int distinctChars1 = 0;
9        int distinctChars2 = 0;
10      
11        // Count characters and track distinct characters in word1
12        for (int i = 0; i < word1.length(); i++) {
13            int charIndex = word1.charAt(i) - 'a';
14            charFrequency1[charIndex]++;
15            // If this is the first occurrence of this character, increment distinct count
16            if (charFrequency1[charIndex] == 1) {
17                distinctChars1++;
18            }
19        }
20      
21        // Count characters and track distinct characters in word2
22        for (int i = 0; i < word2.length(); i++) {
23            int charIndex = word2.charAt(i) - 'a';
24            charFrequency2[charIndex]++;
25            // If this is the first occurrence of this character, increment distinct count
26            if (charFrequency2[charIndex] == 1) {
27                distinctChars2++;
28            }
29        }
30      
31        // Try all possible character swaps between word1 and word2
32        for (int charToSwapFromWord1 = 0; charToSwapFromWord1 < 26; charToSwapFromWord1++) {
33            for (int charToSwapFromWord2 = 0; charToSwapFromWord2 < 26; charToSwapFromWord2++) {
34                // Only consider valid swaps (both characters must exist in their respective strings)
35                if (charFrequency1[charToSwapFromWord1] > 0 && charFrequency2[charToSwapFromWord2] > 0) {
36                  
37                    if (charToSwapFromWord1 == charToSwapFromWord2) {
38                        // Special case: swapping same character doesn't change distinct counts
39                        if (distinctChars1 == distinctChars2) {
40                            return true;
41                        }
42                    } else {
43                        // Calculate new distinct count for word1 after swap
44                        int newDistinctChars1 = distinctChars1;
45                        // If removing last occurrence of a character, decrease distinct count
46                        if (charFrequency1[charToSwapFromWord1] == 1) {
47                            newDistinctChars1--;
48                        }
49                        // If adding first occurrence of a character, increase distinct count
50                        if (charFrequency1[charToSwapFromWord2] == 0) {
51                            newDistinctChars1++;
52                        }
53                      
54                        // Calculate new distinct count for word2 after swap
55                        int newDistinctChars2 = distinctChars2;
56                        // If removing last occurrence of a character, decrease distinct count
57                        if (charFrequency2[charToSwapFromWord2] == 1) {
58                            newDistinctChars2--;
59                        }
60                        // If adding first occurrence of a character, increase distinct count
61                        if (charFrequency2[charToSwapFromWord1] == 0) {
62                            newDistinctChars2++;
63                        }
64                      
65                        // Check if the swap results in equal distinct character counts
66                        if (newDistinctChars1 == newDistinctChars2) {
67                            return true;
68                        }
69                    }
70                }
71            }
72        }
73      
74        // No valid swap found that equalizes distinct character counts
75        return false;
76    }
77}
78

1class Solution {
2public:
3    bool isItPossible(string word1, string word2) {
4        // Arrays to store character frequency for both strings
5        int charFreq1[26]{};  // Frequency array for word1
6        int charFreq2[26]{};  // Frequency array for word2
7      
8        // Count distinct characters in each word
9        int distinctChars1 = 0;
10        int distinctChars2 = 0;
11      
12        // Count character frequencies and distinct characters for word1
13        for (char& ch : word1) {
14            int charIndex = ch - 'a';
15            if (++charFreq1[charIndex] == 1) {
16                // First occurrence of this character
17                ++distinctChars1;
18            }
19        }
20      
21        // Count character frequencies and distinct characters for word2
22        for (char& ch : word2) {
23            int charIndex = ch - 'a';
24            if (++charFreq2[charIndex] == 1) {
25                // First occurrence of this character
26                ++distinctChars2;
27            }
28        }
29      
30        // Try all possible character swaps between word1 and word2
31        for (int i = 0; i < 26; ++i) {
32            for (int j = 0; j < 26; ++j) {
33                // Only consider swap if both characters exist in their respective words
34                if (charFreq1[i] > 0 && charFreq2[j] > 0) {
35                  
36                    if (i == j) {
37                        // Swapping same character doesn't change distinct count
38                        if (distinctChars1 == distinctChars2) {
39                            return true;
40                        }
41                    } else {
42                        // Calculate new distinct count for word1 after swap
43                        // Remove char i from word1, add char j to word1
44                        int newDistinct1 = distinctChars1;
45                        newDistinct1 -= (charFreq1[i] == 1 ? 1 : 0);  // Lose distinct if only one occurrence
46                        newDistinct1 += (charFreq1[j] == 0 ? 1 : 0);  // Gain distinct if didn't have this char
47                      
48                        // Calculate new distinct count for word2 after swap
49                        // Remove char j from word2, add char i to word2
50                        int newDistinct2 = distinctChars2;
51                        newDistinct2 -= (charFreq2[j] == 1 ? 1 : 0);  // Lose distinct if only one occurrence
52                        newDistinct2 += (charFreq2[i] == 0 ? 1 : 0);  // Gain distinct if didn't have this char
53                      
54                        // Check if swap results in equal distinct character counts
55                        if (newDistinct1 == newDistinct2) {
56                            return true;
57                        }
58                    }
59                }
60            }
61        }
62      
63        // No valid swap found
64        return false;
65    }
66};
67

1/**
2 * Determines if it's possible to swap one character from word1 with one character from word2
3 * such that both words have the same number of distinct characters
4 * @param word1 - First input string
5 * @param word2 - Second input string
6 * @returns true if such a swap is possible, false otherwise
7 */
8function isItPossible(word1: string, word2: string): boolean {
9    // Initialize frequency arrays for 26 lowercase letters
10    const frequencyWord1: number[] = Array(26).fill(0);
11    const frequencyWord2: number[] = Array(26).fill(0);
12  
13    // Track distinct character counts for both words
14    let distinctCountWord1 = 0;
15    let distinctCountWord2 = 0;
16
17    // Count character frequencies and distinct characters in word1
18    for (const char of word1) {
19        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
20        frequencyWord1[charIndex]++;
21        // If this is the first occurrence of this character, increment distinct count
22        if (frequencyWord1[charIndex] === 1) {
23            distinctCountWord1++;
24        }
25    }
26
27    // Count character frequencies and distinct characters in word2
28    for (const char of word2) {
29        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
30        frequencyWord2[charIndex]++;
31        // If this is the first occurrence of this character, increment distinct count
32        if (frequencyWord2[charIndex] === 1) {
33            distinctCountWord2++;
34        }
35    }
36
37    // Try all possible character swaps between word1 and word2
38    for (let charIndexFromWord1 = 0; charIndexFromWord1 < 26; charIndexFromWord1++) {
39        for (let charIndexFromWord2 = 0; charIndexFromWord2 < 26; charIndexFromWord2++) {
40            // Only consider valid swaps (both characters must exist in their respective words)
41            if (frequencyWord1[charIndexFromWord1] > 0 && frequencyWord2[charIndexFromWord2] > 0) {
42              
43                // Case 1: Swapping the same character between words
44                if (charIndexFromWord1 === charIndexFromWord2) {
45                    // Distinct counts remain unchanged, check if they're already equal
46                    if (distinctCountWord1 === distinctCountWord2) {
47                        return true;
48                    }
49                } 
50                // Case 2: Swapping different characters between words
51                else {
52                    // Calculate new distinct count for word1 after swap
53                    let newDistinctCountWord1 = distinctCountWord1;
54                    // Lose a distinct char if it only appears once
55                    if (frequencyWord1[charIndexFromWord1] === 1) {
56                        newDistinctCountWord1--;
57                    }
58                    // Gain a distinct char if it doesn't exist yet
59                    if (frequencyWord1[charIndexFromWord2] === 0) {
60                        newDistinctCountWord1++;
61                    }
62                  
63                    // Calculate new distinct count for word2 after swap
64                    let newDistinctCountWord2 = distinctCountWord2;
65                    // Lose a distinct char if it only appears once
66                    if (frequencyWord2[charIndexFromWord2] === 1) {
67                        newDistinctCountWord2--;
68                    }
69                    // Gain a distinct char if it doesn't exist yet
70                    if (frequencyWord2[charIndexFromWord1] === 0) {
71                        newDistinctCountWord2++;
72                    }
73                  
74                    // Check if the swap results in equal distinct counts
75                    if (newDistinctCountWord1 === newDistinctCountWord2) {
76                        return true;
77                    }
78                }
79            }
80        }
81    }
82
83    // No valid swap found
84    return false;
85}
86

Time and Space Complexity

Time Complexity: O(m + n + |Σ|²), where m and n are the lengths of strings word1 and word2 respectively, and |Σ| is the size of the character set (26 for lowercase letters).

Creating Counter objects for both strings takes O(m + n) time
The nested loops iterate through unique characters in each counter, which is at most |Σ| characters each, resulting in O(|Σ|²) iterations
Each iteration performs constant time operations: checking equality, arithmetic operations, and dictionary lookups
Total time complexity: O(m + n + |Σ|²) = O(m + n + 26²) = O(m + n + 676) = O(m + n)

Space Complexity: O(|Σ|), where |Σ| is the size of the character set (26 for lowercase letters).

Two Counter objects store at most |Σ| unique characters each: O(|Σ|) space
Variables x, y, c1, c2, v1, v2, a, and b use constant space: O(1)
Total space complexity: O(|Σ|) = O(26) = O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Handling Character Existence Checks

The Problem: A common mistake is not properly checking whether a character exists in the Counter before accessing it. While Python's Counter returns 0 for non-existent keys (making char_count_1[char_2] == 0 safe), developers might mistakenly use conditions like:

char_2 not in char_count_1 instead of char_count_1[char_2] == 0
char_2 in char_count_1 instead of char_count_1[char_2] > 0

This becomes problematic because Counter objects include all accessed keys with zero values after querying them, which can lead to confusion.

Solution: Consistently use frequency comparisons (== 0 or > 0) rather than membership tests (in or not in) when working with Counters for clarity and correctness.

Pitfall 2: Forgetting the Same Character Swap Case

The Problem: Many developers focus only on swapping different characters and forget that swapping identical characters is a valid operation. For example, swapping an 'a' from word1 with an 'a' from word2 is allowed and doesn't change the distinct character counts.

Incorrect approach:

for char_1, freq_1 in char_count_1.items():
    for char_2, freq_2 in char_count_2.items():
        if char_1 != char_2:  # Only considering different characters
            # Calculate new distinct counts...

Solution: Always include the case where char_1 == char_2. When characters are the same, the distinct counts remain unchanged, so simply check if they're already equal.

Pitfall 3: Incorrect Distinct Count Calculations After Swap

The Problem: The logic for updating distinct counts is subtle. Common mistakes include:

Forgetting that removing the last occurrence of a character decreases the distinct count
Forgetting that adding a new character (that didn't exist before) increases the distinct count
Using wrong conditions like freq_1 <= 1 instead of freq_1 == 1

Incorrect calculation example:

# Wrong: doesn't account for whether character disappears completely
new_distinct_1 = distinct_count_1 - 1 + (char_count_1[char_2] == 0)

# Wrong: uses <= instead of ==
new_distinct_1 = distinct_count_1 - (freq_1 <= 1) + (char_count_1[char_2] == 0)

Solution: Use precise conditions:

Subtract 1 only when freq == 1 (the character will completely disappear)
Add 1 only when the incoming character doesn't exist (frequency is 0)

Pitfall 4: Early Return Optimization Gone Wrong

The Problem: Some might try to optimize by checking if it's impossible to equalize distinct counts before enumeration:

if abs(distinct_count_1 - distinct_count_2) > 2:
    return False  # This is incorrect!

This is wrong because a single swap can change distinct counts by more than 2 in total. For example:

If word1 loses a unique character (-1) and gains a new character (+1): net change = 0
If word2 loses a unique character (-1) and gains a new character (+1): net change = 0
But the difference between the two can still be resolved

Solution: Don't add premature optimizations based on the difference in distinct counts. The full enumeration is necessary and already efficient enough with O(26²) character pairs to check.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: