Make Number of Distinct Characters Equal - Solution & Explanation
Problem Statement
You are given two 0-indexed strings word1 and word2.
A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].
Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.
Example 1:
Input: word1 = "ac", word2 = "b" Output: false Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.
Example 2:
Input: word1 = "abcc", word2 = "aab" Output: true Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.
Example 3:
Input: word1 = "abcde", word2 = "fghij" Output: true Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.
Constraints:
1 <= word1.length, word2.length <= 105word1andword2consist of only lowercase English letters.
Approach Overview
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.
Approach 1: Approach 1: Brute Force with Set Operations
This approach systematically attempts all possible character swaps between the two strings and checks if they lead to equal distinct character counts. While this is not optimal, it serves to illustrate the swap process clearly, leveraging set operations to easily compute the distinct character counts.
The code iterates over each possible swap between characters of word1 and word2. It uses sets to represent the distinct characters and analyzes the impacts of each swap. It stops and returns true if a swap allows both strings to have equal distinct character counts. Otherwise, it returns false.
Code
Python
Complexity
Time Complexity: O(n*m) - where n is the length of word1 and m is the length of word2, as we try all possible swaps.
Space Complexity: O(1) - aside from input and sets of size at most 26 (the number of letters in the alphabet).
Approach 2: Approach 2: Optimized Swap Analysis
This optimized approach leverages the observation that only swapping differing characters influences the distinct character count. For efficiency, it utilizes character frequency and state changes per swap to determine whether the swap makes the number of distinct characters equal between the words. This approach carefully tracks when increments and decrements in distinct counts occur and determines equality before actually executing a swap.
The Java code uses two sets to hold the distinct characters of each string. It goes through each potential swap, evaluating how it would impact the count of distinct characters if it were executed. The key lies in calculating the change in difference in the number of distinct characters and not actually performing the swap, thus reducing computation.
Code
Java
Complexity
Time Complexity: O(n*m) - though it avoids some redundant computations, making it practically faster.
Space Complexity: O(1) - using sets to track counts only means a space complexity of at most 26 for alphabet characters.
Approach 3: Set Based Swap Difference Approach
Begin by calculating the number of distinct characters in both strings using sets. Iterate over possible characters to swap from both words, and consider how the swapping affects the distinct character counts. To swap effectively, ensure that swapping one character results in a net-zero difference in the count change. This involves leveraging the union-intersection counting of potential new characters.
Check for swap candidates where the removal of one character from a set and addition of another would balance the distinct counts.
This solution makes use of Python sets to store distinct characters from each word. It then evaluates possible swaps of characters between the two sets that result in equal distinct character counts after the swap. The solution ensures the transition maintains the property of distinct character equivalence post-swap.
Code
Python
JavaScript
Complexity
Time Complexity: O(n * m), where n is the length of word1 and m is the length of word2. For each character combination between the two sets, calculate the effect of swaps.
Space Complexity: O(u + v), where u and v are number of unique characters in word1 and word2, respectively.
Approach 4: Count-Based Greedy Check
Instead of directly iterating over character pairs, attempt to adjust the distinct count via examining count differences directly. Leverage character frequencies and explore scenarios where direct swaps using frequency presence can balance the distinct counts effectively. This avoids exhaustive checks and focuses on potential viable swaps.
This Java solution harnesses hash sets to store characters of both words distinctly. It primarily utilizes set operations to determine which unique swaps directly lead to equal distinct character counts. By leveraging the comparison of element existence across sets, viable swap opportunities are quickly identified and validated.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of word1 and word2. Unlike the iterative pair approach, this method usually operates in a more efficient manner by directly leveraging set operations.
Space Complexity: O(u + v), due to unique character sets required for the solution.
Approach 5: Counting + Enumeration
We first use two arrays cnt1 and cnt2 of length 26 to record the frequency of each character in the strings word1 and word2, respectively.
Then, we count the number of distinct characters in word1 and word2, denoted as x and y respectively.
Next, we enumerate each character c1 in word1 and each character c2 in word2. If c1 = c2, we only need to check if x and y are equal; otherwise, we need to check if x - (cnt1[c1] = 1) + (cnt1[c2] = 0) and y - (cnt2[c2] = 1) + (cnt2[c1] = 0) are equal. If they are equal, then we have found a solution and return true.
If we have enumerated all characters and have not found a suitable solution, we return false.
The time complexity is O(m + n + |\Sigma|^2), where m and n are the lengths of the strings word1 and word2, and \Sigma is the character set. In this problem, the character set consists of lowercase letters, so |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Set Operations | Time Complexity: O(n*m) - where n is the length of |
| Approach 2: Optimized Swap Analysis | Time Complexity: O(n*m) - though it avoids some redundant computations, making it practically faster. |
| Set Based Swap Difference Approach | Time Complexity: O(n * m), where n is the length of |
| Count-Based Greedy Check | Time Complexity: O(n + m), where n and m are the lengths of word1 and word2. Unlike the iterative pair approach, this method usually operates in a more efficient manner by directly leveraging set operations. |
| Counting + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set Operations | O(n * m) | O(26) | Simple baseline implementation or for validating logic |
| Optimized Swap Analysis | O(26^2) | O(26) | General optimal solution using frequency arrays |
| Set Based Swap Difference | O(26^2) | O(26) | When reasoning about distinct characters directly using sets |
| Count-Based Greedy Check | O(26^2) | O(26) | Interview-preferred solution with minimal operations |
Video Solution
Make Number of Distinct Characters Equal | leetcode Weekly 327 | Leetcode Medium • BinaryMagic • 1,902 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Number of Distinct Characters Equal easy or hard?
Make Number of Distinct Characters Equal Python/Java solution
How to solve Make Number of Distinct Characters Equal in O(n)?
What is the best approach for Make Number of Distinct Characters Equal?
Is Make Number of Distinct Characters Equal asked at Google/Amazon/Meta?
What data structure is used in Make Number of Distinct Characters Equal?
What is the time complexity of Make Number of Distinct Characters Equal?
Ready to solve this problem?
Practice Make Number of Distinct Characters Equal with our built-in code editor and test cases.
Practice on FleetCode