Skip to content

2531. Make Number of Distinct Characters Equal

Difficulty Topics

Description

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.

Solution

make-number-of-distinct-characters-equal.py
class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        cnt1 = [0] * 26
        cnt2 = [0] * 26

        for x in word1:
            cnt1[ord(x) - ord('a')] += 1

        for x in word2:
            cnt2[ord(x) - ord('a')] += 1

        def check(cnt1, cnt2):
            return sum(1 for x in cnt1 if x > 0) == sum(1 for x in cnt2 if x > 0)

        for a in range(26):
            for b in range(26):
                if cnt1[a] > 0 and cnt2[b] > 0:
                    # if a in word1 swap with b in word2
                    cnt1[a] -= 1
                    cnt1[b] += 1

                    cnt2[a] += 1
                    cnt2[b] -= 1

                    if check(cnt1, cnt2):
                        return True

                    cnt1[a] += 1
                    cnt1[b] -= 1

                    cnt2[a] -= 1
                    cnt2[b] += 1

        return False