Make Number of Distinct Characters Equal

Make Number of Distinct Characters Equal

What is this problem about?

The Make Number of Distinct Characters Equal problem provides two strings, word1 and word2. You must choose exactly one character from word1 and exactly one character from word2 and swap them. The goal is to determine if it is possible to make the number of distinct characters in both strings exactly equal after performing this single swap.

Why is this asked in interviews?

This is a highly popular Hash Map and Matrix problem. Interviewers ask it because it tests a candidate's ability to abstract string constraints. Rather than manipulating strings directly (which is slow and error-prone), candidates must realize that since there are only 26 lowercase English letters, the problem space is incredibly small. It perfectly assesses fixed-time optimization.

Algorithmic pattern used

This problem relies on a Frequency Map / Fixed $26 \times 26$ Iteration pattern. First, count the frequencies of characters in both strings into two arrays of size 26. Since you only swap one character from word1 with one from word2, you can simply iterate through all 26 possible characters in word1 and all 26 possible characters in word2. For each pair (char1, char2), if both exist in their respective strings, simulate the swap on the frequency arrays, check if the distinct counts match, and then reverse the simulation.

Example explanation

word1 = "ab", word2 = "cd". Both currently have 2 distinct characters. Freq1: a:1, b:1. Freq2: c:1, d:1. Let's test swapping 'a' from word1 and 'c' from word2.

• Remove 'a' from Freq1 (a becomes 0). Add 'c' to Freq1 (c becomes 1). Distinct in word1 remains 2 (b, c).
• Remove 'c' from Freq2 (c becomes 0). Add 'a' to Freq2 (a becomes 1). Distinct in word2 remains 2 (d, a).
• Distinct counts are 2 and 2. They are equal! Return true.

If word1 = "a", word2 = "bb". Distinct: 1 and 1. Swap 'a' and 'b':

• word1 loses 'a', gains 'b'. Distinct: 1 ('b').
• word2 loses 'b' (has 1 left), gains 'a'. Distinct: 2 ('b', 'a').
• 1 != 2. We try all combinations, none work. Return false.

Common mistakes candidates make

The biggest trap is trying to solve this by checking lengths or using heuristics based on the difference in distinct counts. There are too many edge cases (like swapping identical characters, or swapping a character that exists multiple times versus one that exists uniquely). Another mistake is trying to manipulate strings directly using substring or replace, which results in Time Limit Exceeded.

Interview preparation tip

To ace the Make Number of Distinct Characters Equal coding problem, embrace the power of the 26x26 constant time loop. Whenever a string problem restricts the alphabet to lowercase letters and asks for a single operation, simulating every possible alphabet combination on frequency arrays is an $O(N)$ solution that is mathematically bulletproof and easy to implement.