# Make Number of Distinct Characters Equal **Difficulty:** MEDIUM [External](https://leetcode.com/problems/make-number-of-distinct-characters-equal) Canonical: https://scaleengineer.com/dsa/problems/make-number-of-distinct-characters-equal **Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting) **Data structures:** Hash Table, String --- ## Problem 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 <= 105` * `word1` and `word2` consist of only lowercase English letters. # Approaches ## Brute-Force Simulation by Swapping Indices This approach directly simulates the process described in the problem. It considers every possible pair of characters to swap, one from `word1` and one from `word2`. For each pair of indices `(i, j)`, it creates new versions of `word1` and `word2` with `word1[i]` and `word2[j]` swapped. Then, it calculates the number of distinct characters in these new strings. If the counts are equal, it means a valid swap is found, and the function returns `true`. If all possible swaps are checked without finding a match, it returns `false`. **Time:** O(L1 * L2 * (L1 + L2)), where L1 and L2 are the lengths of `word1` and `word2`. The nested loops run `L1 * L2` times. Inside the loop, creating new strings and counting distinct characters takes `O(L1 + L2)` time. · **Space:** O(L1 + L2), where L1 and L2 are the lengths of the strings. This space is used to store the new strings created in each iteration. **Pros:** Simple to understand and implement.; Directly follows the problem statement. **Cons:** Extremely slow due to its high time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation The brute-force method involves a nested loop structure. The outer loop iterates through every character of `word1`, and the inner loop iterates through every character of `word2`. For each pair of characters, we perform the swap. This requires creating new string objects (or mutable string builders) for the modified strings. After the swap, we compute the number of unique characters for each of the two new strings, typically by adding all characters to a `HashSet` and checking its size. If the sizes are equal, we've found a solution. ```java class Solution { public boolean isItPossible(String word1, String word2) { for (int i = 0; i < word1.length(); i++) { for (int j = 0; j < word2.length(); j++) { char c1 = word1.charAt(i); char c2 = word2.charAt(j); StringBuilder sb1 = new StringBuilder(word1); sb1.setCharAt(i, c2); String newWord1 = sb1.toString(); StringBuilder sb2 = new StringBuilder(word2); sb2.setCharAt(j, c1); String newWord2 = sb2.toString(); if (countDistinct(newWord1) == countDistinct(newWord2)) { return true; } } } return false; } private int countDistinct(String s) { java.util.Set set = new java.util.HashSet<>(); for (char c : s.toCharArray()) { set.add(c); } return set.size(); } } ``` ### Algorithm * Iterate through each index `i` from `0` to `word1.length() - 1`. * Inside this loop, iterate through each index `j` from `0` to `word2.length() - 1`. * Create a new string `newWord1` by swapping the character at `word1[i]` with `word2[j]`. * Create a new string `newWord2` by swapping the character at `word2[j]` with `word1[i]`. * Use a helper function or a `HashSet` to count the number of distinct characters in `newWord1` and `newWord2`. * If the two counts are equal, return `true`. * If the loops complete, it means no such swap exists, so return `false`. ## Frequency Counting and Character Type Iteration This is a highly optimized approach that avoids iterating through all index pairs. The key insight is that the effect of a swap on the distinct character count depends only on the types of characters being swapped, not their positions. We can iterate through all 26*26 possible pairs of character types `(c1, c2)`. For each pair, we check if `c1` exists in `word1` and `c2` exists in `word2`. If so, we simulate the swap by manipulating frequency counts and check if the resulting distinct character counts are equal. **Time:** O(L1 + L2), where L1 and L2 are the lengths of the strings. Populating the frequency maps takes `O(L1 + L2)`. The nested loops run a constant number of times (`26 * 26 = 676`). Inside the loop, all operations are constant time. Thus, the total complexity is dominated by the initial frequency counting. · **Space:** O(1), as the frequency arrays have a constant size of 26, independent of the input string lengths. **Pros:** Extremely efficient and optimal for the given constraints.; Handles large inputs easily due to linear time complexity. **Cons:** The logic is slightly more complex to devise compared to the brute-force approach. ### Explanation Instead of iterating through `O(L1 * L2)` index pairs, we can iterate through `26 * 26` character type pairs. First, we pre-compute the frequency of each character in both strings using arrays of size 26. Then, we loop through all possible characters `c1` from 'a' to 'z' to be swapped from `word1`, and for each `c1`, we loop through all possible characters `c2` from 'a' to 'z' to be swapped from `word2`. For a given pair `(c1, c2)`, we first check if `word1` contains `c1` and `word2` contains `c2`. If so, we simulate the swap by updating the frequency arrays. After updating, we count the number of distinct characters in each hypothetical new string by checking how many entries in the frequency arrays are greater than zero. If these counts are equal, we return `true`. It's crucial to revert the changes made to the frequency arrays (backtrack) before checking the next pair, ensuring each simulation starts from the original state. ```java class Solution { public boolean isItPossible(String word1, String word2) { int[] freq1 = new int[26]; for (char c : word1.toCharArray()) { freq1[c - 'a']++; } int[] freq2 = new int[26]; for (char c : word2.toCharArray()) { freq2[c - 'a']++; } for (int i = 0; i < 26; i++) { // char c1 from word1 for (int j = 0; j < 26; j++) { // char c2 from word2 if (freq1[i] > 0 && freq2[j] > 0) { // Simulate swap freq1[i]--; freq2[j]--; freq1[j]++; freq2[i]++; int d1 = 0, d2 = 0; for (int k = 0; k < 26; k++) { if (freq1[k] > 0) d1++; if (freq2[k] > 0) d2++; } if (d1 == d2) { return true; } // Backtrack to restore original frequencies freq1[i]++; freq2[j]++; freq1[j]--; freq2[i]--; } } } return false; } } ``` ### Algorithm * Create two frequency arrays, `freq1` and `freq2`, of size 26. * Populate `freq1` and `freq2` by iterating through `word1` and `word2`. * Iterate through all possible character types `c1` (from 'a' to 'z') to be taken from `word1`. * Inside, iterate through all possible character types `c2` (from 'a' to 'z') to be taken from `word2`. * Check if this swap is possible (i.e., `freq1[c1] > 0` and `freq2[c2] > 0`). * If possible, simulate the swap by adjusting the frequency counts: `freq1[c1]--`, `freq2[c2]--`, `freq1[c2]++`, `freq2[c1]++`. * After the simulated swap, calculate the new number of distinct characters for both frequency maps by counting non-zero entries. * If the new distinct counts are equal, a valid swap is found, so return `true`. * Undo the changes to the frequency maps (backtrack) so the next iteration starts with the original frequencies. * If all character pairs are checked without success, return `false`. # Solutions ### Java ```java class Solution { public boolean isItPossible(String word1, String word2) { int[] cnt1 = new int[26]; int[] cnt2 = new int[26]; for (int i = 0; i < word1.length(); ++i) { ++cnt1[word1.charAt(i) - 'a']; } for (int i = 0; i < word2.length(); ++i) { ++cnt2[word2.charAt(i) - 'a']; } for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { if (cnt1[i] > 0 && cnt2[j] > 0) { --cnt1[i]; --cnt2[j]; ++cnt1[j]; ++cnt2[i]; int d = 0; for (int k = 0; k < 26; ++k) { if (cnt1[k] > 0) { ++d; } if (cnt2[k] > 0) { --d; } } if (d == 0) { return true; } ++cnt1[i]; ++cnt2[j]; --cnt1[j]; --cnt2[i]; } } } return false; } } ``` ### CPP ```cpp class Solution { public: bool isItPossible(string word1, string word2) { int cnt1[26]{}; int cnt2[26]{}; for (char &c : word1) { ++cnt1[c - 'a']; } for (char &c : word2) { ++cnt2[c - 'a']; } for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { if (cnt1[i] > 0 && cnt2[j] > 0) { --cnt1[i]; --cnt2[j]; ++cnt1[j]; ++cnt2[i]; int d = 0; for (int k = 0; k < 26; ++k) { if (cnt1[k] > 0) { ++d; } if (cnt2[k] > 0) { --d; } } if (d == 0) { return true; } ++cnt1[i]; ++cnt2[j]; --cnt1[j]; --cnt2[i]; } } } return false; } }; ``` ### Python ```python class Solution: def isItPossible(self, word1: str, word2: str) -> bool: cnt1 = [0] * 26 cnt2 = [0] * 26 for c in word1: cnt1[ord(c) - ord('a')] += 1 for c in word2: cnt2[ord(c) - ord('a')] += 1 for i, a in enumerate(cnt1): for j, b in enumerate(cnt2): if a and b: cnt1[i], cnt2[j] = cnt1[i] - 1, cnt2[j] - 1 cnt1[j], cnt2[i] = cnt1[j] + 1, cnt2[i] + 1 if sum(v > 0 for v in cnt1) == sum(v > 0 for v in cnt2): return True cnt1[i], cnt2[j] = cnt1[i] + 1, cnt2[j] + 1 cnt1[j], cnt2[i] = cnt1[j] - 1, cnt2[i] - 1 return False ```