Skip to content

2531. Make Number of Distinct Characters Equal

  • Time: $O(26^2 + |\texttt{word1}| + |\texttt{word2}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  bool isItPossible(string word1, string word2) {
    const vector<int> count1 = getCount(word1);
    const vector<int> count2 = getCount(word2);
    const int distinct1 = getDistinct(count1);
    const int distinct2 = getDistinct(count2);

    for (int i = 0; i < 26; ++i)
      for (int j = 0; j < 26; ++j) {
        if (count1[i] == 0 || count2[j] == 0)
          continue;
        if (i == j) {
          // Swapping the same letters won't change the number of distinct
          // letters in each string, so just check if `distinct1 == distinct2`.
          if (distinct1 == distinct2)
            return true;
          continue;
        }
        // The calculation is meaningful only when i != j.
        // Swap ('a' + i) in word1 with ('a' + j) in word2.
        const int distinctAfterSwap1 =
            distinct1 - (count1[i] == 1) + (count1[j] == 0);
        const int distinctAfterSwap2 =
            distinct2 - (count2[j] == 1) + (count2[i] == 0);
        if (distinctAfterSwap1 == distinctAfterSwap2)
          return true;
      }

    return false;
  }

 private:
  vector<int> getCount(const string& s) {
    vector<int> count(26);
    for (const char c : s)
      ++count[c - 'a'];
    return count;
  }

  int getDistinct(const vector<int>& count) {
    return ranges::count_if(count, [](const int c) { return c > 0; });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
  public boolean isItPossible(String word1, String word2) {
    final int[] count1 = getCount(word1);
    final int[] count2 = getCount(word2);
    final int distinct1 = getDistinct(count1);
    final int distinct2 = getDistinct(count2);

    for (int i = 0; i < 26; ++i)
      for (int j = 0; j < 26; ++j) {
        if (count1[i] == 0 || count2[j] == 0)
          continue;
        if (i == j) {
          // Swapping the same letters won't change the number of distinct
          // letters in each string, so just check if `distinct1 == distinct2`.
          if (distinct1 == distinct2)
            return true;
          continue;
        }
        // The calculation is meaningful only when i != j.
        // Swap ('a' + i) in word1 with ('a' + j) in word2.
        final int distinctAfterSwap1 =
            distinct1 - (count1[i] == 1 ? 1 : 0) + (count1[j] == 0 ? 1 : 0);
        final int distinctAfterSwap2 =
            distinct2 - (count2[j] == 1 ? 1 : 0) + (count2[i] == 0 ? 1 : 0);
        if (distinctAfterSwap1 == distinctAfterSwap2)
          return true;
      }

    return false;
  }

  private int[] getCount(final String s) {
    int[] count = new int[26];
    for (final char c : s.toCharArray())
      ++count[c - 'a'];
    return count;
  }

  private int getDistinct(int[] count) {
    return (int) Arrays.stream(count).filter(c -> c > 0).count();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def isItPossible(self, word1: str, word2: str) -> bool:
    count1 = collections.Counter(word1)
    count2 = collections.Counter(word2)
    distinct1 = len(count1)
    distinct2 = len(count2)

    for a in count1:
      for b in count2:
        if a == b:
          # Swapping the same letters won't change the number of distinct
          # letters in each string, so just check if `distinct1 == distinct2`.
          if distinct1 == distinct2:
            return True
          continue
        # The calculation is meaningful only when a != b
        # Swap a in word1 with b in word2.
        distinctAfterSwap1 = distinct1 - (count1[a] == 1) + (count1[b] == 0)
        distinctAfterSwap2 = distinct2 - (count2[b] == 1) + (count2[a] == 0)
        if distinctAfterSwap1 == distinctAfterSwap2:
          return True

    return False