#2531

Medium

LeetCode Problem Workspace

Make Number of Distinct Characters Equal

Determine if a single swap can equalize distinct character counts between two strings using hash tables for tracking frequencies.

hash table string counting

Problem Statement

Given two strings word1 and word2, determine if it is possible to make the number of distinct characters in both strings equal with exactly one swap. Each swap exchanges one character from word1 with one from word2.

A move consists of picking any index i in word1 and any index j in word2, swapping word1[i] with word2[j]. Return true if after one swap both strings have the same number of distinct characters; otherwise, return false. Strings contain only lowercase English letters.

Examples

Example 1

Input: word1 = "ac", word2 = "b"

Output: false

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

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

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 Approach

Build Frequency Maps

Count the occurrences of each character in word1 and word2 using hash tables. This helps identify distinct characters and duplicates, which is critical to determine valid swaps that could equalize counts.

Evaluate Potential Swaps

Iterate over characters in both frequency maps. For each pair of characters, simulate swapping them and update the distinct counts. Check if the swap produces equal numbers of distinct characters in both strings.

Optimize with Early Checks

If the difference in distinct character counts is greater than 2, return false immediately. Also, consider swaps that move duplicates or unique characters strategically to minimize unnecessary calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of unique characters in each string, typically O(26*26) due to limited lowercase letters, and space complexity is O(26) per string for frequency maps.

What Interviewers Usually Probe

Pay attention to edge cases where one string has only duplicates.
Watch for off-by-one errors when counting distinct characters after a swap.
Consider how swapping identical characters affects distinct counts.

Common Pitfalls or Variants

Common pitfalls

Assuming any swap will work without checking distinct counts.
Failing to handle swaps involving characters already present in both strings.
Overlooking the need to update counts after each simulated swap.

Follow-up variants

Allow multiple swaps to equalize distinct characters instead of exactly one.
Limit swaps to adjacent characters only and evaluate feasibility.
Consider uppercase and lowercase letters, increasing the character set size.

FAQ

What is the main strategy for Make Number of Distinct Characters Equal?

Use hash tables to count character frequencies in both strings and simulate swaps to check if distinct counts can match.

Can I solve this problem without hash tables?

Technically yes, but hash tables simplify tracking distinct characters and duplicates, making the solution efficient.

What happens if both strings already have equal distinct characters?

You still need to check if a swap can maintain equality; some swaps may break it if duplicates are swapped.

Are there limits on string lengths?

Yes, each string has length between 1 and 105 characters, consisting only of lowercase English letters.

How does counting duplicates help in this problem?

Duplicates determine which swaps affect distinct counts and which swaps are ineffective, guiding valid move selection.

terminal

Solution

Solution 1: Counting + Enumeration

We first use two arrays $\textit{cnt1}$ and $\textit{cnt2}$ of length $26$ to record the frequency of each character in the strings $\textit{word1}$ and $\textit{word2}$, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        cnt1 = Counter(word1)
        cnt2 = Counter(word2)
        x, y = len(cnt1), len(cnt2)
        for c1, v1 in cnt1.items():
            for c2, v2 in cnt2.items():
                if c1 == c2:
                    if x == y:
                        return True
                else:
                    a = x - (v1 == 1) + (cnt1[c2] == 0)
                    b = y - (v2 == 1) + (cnt2[c1] == 0)
                    if a == b:
                        return True
        return False

Continue Practicing

#2514 count anagrams #2506 count pairs of similar strings #2423 remove letter to equalize frequency