# 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 count1 = getCount(word1); const vector 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 getCount(const string& s) { vector count(26); for (const char c : s) ++count[c - 'a']; return count; } int getDistinct(const vector& 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