Make Number of Distinct Characters Equal
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Iterate through each index
ifrom0toword1.length() - 1. - Inside this loop, iterate through each index
jfrom0toword2.length() - 1. - Create a new string
newWord1by swapping the character atword1[i]withword2[j]. - Create a new string
newWord2by swapping the character atword2[j]withword1[i]. - Use a helper function or a
HashSetto count the number of distinct characters innewWord1andnewWord2. - If the two counts are equal, return
true. - If the loops complete, it means no such swap exists, so return
false.
Walkthrough
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.
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<Character> set = new java.util.HashSet<>(); for (char c : s.toCharArray()) { set.add(c); } return set.size(); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create two frequency arrays,
freq1andfreq2, of size 26. - Populate
freq1andfreq2by iterating throughword1andword2. - Iterate through all possible character types
c1(from 'a' to 'z') to be taken fromword1. - Inside, iterate through all possible character types
c2(from 'a' to 'z') to be taken fromword2. - Check if this swap is possible (i.e.,
freq1[c1] > 0andfreq2[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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.