Make Number of Distinct Characters Equal - Video Solutions

Problem Overview: You are given two strings and can swap exactly one character between them. The goal is to determine whether a single swap can make the number of distinct characters in both strings equal.

The challenge is not the swap itself but predicting how the swap changes the distinct counts. Adding a character may increase the distinct set, while removing the last occurrence of a character may decrease it. Efficient solutions track these frequency changes using hash tables or frequency arrays instead of rebuilding sets repeatedly.

Approach 1: Brute Force with Set Operations (O(n * m), space O(26))

Try every possible swap between characters in word1 and word2. For each pair of indices, simulate the swap and compute the number of distinct characters using a set. If both sets end up with the same size, return true. This approach directly models the problem and is easy to reason about, but repeatedly constructing sets makes it inefficient for larger inputs. Still useful as a baseline to validate logic during development.

Approach 2: Optimized Swap Analysis (O(26^2) time, O(26) space)

Instead of trying every position, track character frequencies using arrays or a counting map. Iterate over all possible characters from 'a' to 'z' in both strings. For each potential swap pair, compute how the distinct counts change: removing the last occurrence decreases the count, while introducing a new character increases it. Because the alphabet size is fixed, the search space is only 26 × 26, making this approach effectively constant time.

Set Based Swap Difference Approach (O(26^2) time, O(26) space)

This method maintains two sets representing distinct characters in each string. For each candidate character swap, simulate how the sets would change without modifying the original strings. If the swapped character already exists in the target set, the distinct count stays the same; otherwise it increases. Similarly, removing a character that appears only once reduces the count. This approach focuses directly on distinct set sizes instead of full frequency recalculation.

Count-Based Greedy Check (O(26^2) time, O(26) space)

The most interview-friendly solution uses two frequency arrays and precomputed distinct counts. Iterate through all character pairs that actually appear in the strings. For each pair, compute the resulting distinct counts after the swap using simple arithmetic rules on the frequency values. This avoids rebuilding sets and minimizes branching logic. Because only 26 letters are considered, the runtime remains constant and the implementation is concise.

Recommended for interviews: Start by describing the brute force swap simulation to demonstrate understanding of the problem mechanics. Then move to the frequency-based swap analysis. Interviewers expect the optimized counting approach because it leverages constant alphabet size and avoids rebuilding sets.