Make Number of Distinct Characters Equal — Solution
Make Number of Distinct Characters Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Make Number of Distinct Characters Equal is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two lowercase strings word1 and word2. A move picks an index i of word1 and an index j of word2 and swaps the characters word1[i] and word2[j].
Return true if it is possible to make the number of distinct characters in word1 equal to the number of distinct characters in word2 with exactly one move, and false otherwise.
Example 1
Input: word1 = "aab", word2 = "cd"
Output: true
Explanation: Swap the `b` of `word1` with the `c` of `word2`: `"aac"` and `"bd"` both have 2 distinct characters.
Example 2
Input: word1 = "ab", word2 = "abcc"
Output: false
Explanation: No single swap brings the counts (2 and 3) together.
Example 3
Input: word1 = "a", word2 = "a"
Output: true
Explanation: Swapping `a` with `a` changes nothing, and both already have 1.
Constraints
1 <= word1.length, word2.length <= 10^5word1 and word2 consist of only lowercase English letters
Hints for Make Number of Distinct Characters Equal
Hint 1
The strings can be long, but a swap is fully described by which letter leaves
word1and which letter leavesword2— at most 26 × 26 choices.Hint 2
Keep letter counts for both words. How does swapping letter
x(fromword1) with lettery(fromword2) change each distinct count?Hint 3
If
x == ynothing changes. Otherwiseword1losesxas a distinct letter if it had only one, and gainsyif it had none; symmetrically forword2. Check every pair of present letters.
How to solve Make Number of Distinct Characters Equal
Only letters matter, not positions: try every pair (letter x present in word1, letter y present in word2) and update the two distinct counts in O(1).
Approach
- Count letters of both words; let
d1andd2be the numbers of distinct letters. - For every
xwithc1[x] > 0and everyywithc2[y] > 0: - If
x == y, the swap changes nothing; succeed ifd1 == d2. - Otherwise the new counts are
d1 - [c1[x] == 1] + [c1[y] == 0]andd2 - [c2[y] == 1] + [c2[x] == 0]; succeed if they are equal. - If no pair works, return
false.
Why it works
Swapping word1[i] and word2[j] affects the letter multisets only through the two letters involved, so every index pair with the same letters gives the same outcome; enumerating letter pairs covers all moves. word1 loses one x and gains one y: x disappears from its distinct set exactly when it was its last copy, and y appears exactly when it had none. The same reasoning applies to word2 with the roles reversed.
Complexity
- Time —
O(n + m + 26²) - Space —
O(26)
Pitfalls
- Exactly one move is required: when
x == ythe counts stay as they are, which is fine only if they are already equal. - Update both words: the letter leaving one word arrives in the other.
- Only letters actually present can be picked — skip
xwithc1[x] == 0andywithc2[y] == 0.
Reference solution
Python
def isItPossible(word1: str, word2: str) -> bool:
c1 = [0] * 26
c2 = [0] * 26
for ch in word1:
c1[ord(ch) - 97] += 1
for ch in word2:
c2[ord(ch) - 97] += 1
d1 = sum(1 for v in c1 if v > 0)
d2 = sum(1 for v in c2 if v > 0)
for x in range(26):
if c1[x] == 0:
continue
for y in range(26):
if c2[y] == 0:
continue
if x == y:
if d1 == d2:
return True
continue
n1 = d1 - (1 if c1[x] == 1 else 0) + (1 if c1[y] == 0 else 0)
n2 = d2 - (1 if c2[y] == 1 else 0) + (1 if c2[x] == 0 else 0)
if n1 == n2:
return True
return FalseJava
public static boolean isItPossible(String word1, String word2) {
int[] c1 = new int[26], c2 = new int[26];
for (int i = 0; i < word1.length(); i++) c1[word1.charAt(i) - 'a']++;
for (int i = 0; i < word2.length(); i++) c2[word2.charAt(i) - 'a']++;
int d1 = 0, d2 = 0;
for (int k = 0; k < 26; k++) { if (c1[k] > 0) d1++; if (c2[k] > 0) d2++; }
for (int x = 0; x < 26; x++) {
if (c1[x] == 0) continue;
for (int y = 0; y < 26; y++) {
if (c2[y] == 0) continue;
if (x == y) { if (d1 == d2) return true; continue; }
int n1 = d1 - (c1[x] == 1 ? 1 : 0) + (c1[y] == 0 ? 1 : 0);
int n2 = d2 - (c2[y] == 1 ? 1 : 0) + (c2[x] == 0 ? 1 : 0);
if (n1 == n2) return true;
}
}
return false;
}C++
bool isItPossible(string word1, string word2) {
int c1[26] = {0}, c2[26] = {0};
for (char ch : word1) c1[ch - 'a']++;
for (char ch : word2) c2[ch - 'a']++;
int d1 = 0, d2 = 0;
for (int k = 0; k < 26; k++) { if (c1[k] > 0) d1++; if (c2[k] > 0) d2++; }
for (int x = 0; x < 26; x++) {
if (c1[x] == 0) continue;
for (int y = 0; y < 26; y++) {
if (c2[y] == 0) continue;
if (x == y) { if (d1 == d2) return true; continue; }
int n1 = d1 - (c1[x] == 1 ? 1 : 0) + (c1[y] == 0 ? 1 : 0);
int n2 = d2 - (c2[y] == 1 ? 1 : 0) + (c2[x] == 0 ? 1 : 0);
if (n1 == n2) return true;
}
}
return false;
}JavaScript
var isItPossible = function(word1, word2) {
var c1 = new Array(26).fill(0), c2 = new Array(26).fill(0);
for (var i = 0; i < word1.length; i++) c1[word1.charCodeAt(i) - 97]++;
for (var j = 0; j < word2.length; j++) c2[word2.charCodeAt(j) - 97]++;
var d1 = 0, d2 = 0;
for (var k = 0; k < 26; k++) { if (c1[k] > 0) d1++; if (c2[k] > 0) d2++; }
for (var x = 0; x < 26; x++) {
if (c1[x] === 0) continue;
for (var y = 0; y < 26; y++) {
if (c2[y] === 0) continue;
if (x === y) { if (d1 === d2) return true; continue; }
var n1 = d1 - (c1[x] === 1 ? 1 : 0) + (c1[y] === 0 ? 1 : 0);
var n2 = d2 - (c2[y] === 1 ? 1 : 0) + (c2[x] === 0 ? 1 : 0);
if (n1 === n2) return true;
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets