We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Number of Distinct Characters Equal

Number: 2615

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two strings word1 and word2, you can perform exactly one move consisting of swapping one character from word1 with one character from word2. The goal is to check if it is possible to make the number of distinct characters in word1 and word2 equal after this one swap. The swap is allowed even if the characters being swapped are the same.

Key Insights

  • Only one swap is allowed, so you must calculate the impact of a single swap on the count of distinct characters.
  • Swapping two characters that are identical leaves both strings unchanged. Thus if the distinct counts are already equal, a swap of the same character (present in both strings) immediately gives a valid solution.
  • For different characters a (from word1) and b (from word2), the swap may remove a from a string if it occurs only once and may add a new character if b wasn’t previously present (and vice-versa). Adjust the distinct count accordingly.
  • Since the number of possible letters is limited to 26 (lowercase English letters), iterating over all possible pairs (a, b) is efficient.

Space and Time Complexity

Time Complexity: O(1) — since we iterate over at most 26*26 possible letter pairs. Space Complexity: O(1) — additional space is used only for fixed-size frequency dictionaries.

Solution

The solution involves these steps:

  1. Count the frequency of each character in word1 and word2.
  2. Calculate the number of distinct characters in both strings.
  3. Iterate over each letter a in word1 (present in its frequency dictionary) and each letter b in word2 (present in its frequency dictionary).
    • If a == b and the current distinct counts are equal, a swap of the same character results in no change. Return true.
    • If a != b, simulate the swap:
      • For word1:
        • If a appears only once, swapping it out will reduce the distinct count by 1.
        • If b is not already in word1, swapping it in will increase the distinct count by 1.
      • For word2:
        • Similarly, adjust for losing b (if its count is 1) and adding a (if a is not already present).
    • If the new distinct counts are equal, return true.
  4. Return false if no valid swap is found.

Code Solutions

# Python solution with line-by-line comments
def isItPossible(word1: str, word2: str) -> bool:
    # Build frequency dictionaries for both words
    freq1 = {}
    freq2 = {}
    for ch in word1:
        freq1[ch] = freq1.get(ch, 0) + 1
    for ch in word2:
        freq2[ch] = freq2.get(ch, 0) + 1

    # Calculate the number of distinct letters in each word
    distinct1 = len(freq1)
    distinct2 = len(freq2)

    # Consider each letter present in word1 and word2
    for a in freq1:  # letter from word1
        for b in freq2:  # letter from word2
            # If letters are the same, swapping doesn't change counts
            if a == b:
                if distinct1 == distinct2:
                    return True
            else:
                # Calculate new distinct count for word1 after swapping:
                # Remove letter a: if a appears exactly once, it will be lost
                newDistinct1 = distinct1 - (1 if freq1[a] == 1 else 0)
                # Add letter b: if b doesn't exist originally in word1, it's added
                if b not in freq1:
                    newDistinct1 += 1

                # Calculate new distinct count for word2 after swapping:
                newDistinct2 = distinct2 - (1 if freq2[b] == 1 else 0)
                if a not in freq2:
                    newDistinct2 += 1

                # Check if the new distinct counts match
                if newDistinct1 == newDistinct2:
                    return True
    return False

# Example usage:
# print(isItPossible("abcc", "aab"))
← Back to All Questions