Make Number of Distinct Characters Equal

Medium
1244.

Make Number of Distinct Characters Equal

Make Number of Distinct Characters Equal is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

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^5
  • word1 and word2 consist of only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var isItPossible = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Make Number of Distinct Characters Equal

  1. Hint 1

    The strings can be long, but a swap is fully described by which letter leaves word1 and which letter leaves word2 — at most 26 × 26 choices.

  2. Hint 2

    Keep letter counts for both words. How does swapping letter x (from word1) with letter y (from word2) change each distinct count?

  3. Hint 3

    If x == y nothing changes. Otherwise word1 loses x as a distinct letter if it had only one, and gains y if it had none; symmetrically for word2. 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

  1. Count letters of both words; let d1 and d2 be the numbers of distinct letters.
  2. For every x with c1[x] > 0 and every y with c2[y] > 0:
  3. If x == y, the swap changes nothing; succeed if d1 == d2.
  4. Otherwise the new counts are d1 - [c1[x] == 1] + [c1[y] == 0] and d2 - [c2[y] == 1] + [c2[x] == 0]; succeed if they are equal.
  5. 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 == y the 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 x with c1[x] == 0 and y with c2[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 False

Java

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