Scale Engineer

Make Number of Distinct Characters Equal

Med
#2311Time: 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.
Patterns
Counting
Data structures
Hash TableString

Prompt

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

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 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.

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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem