Make Number of Distinct Characters Equal - Practice Coding Problems

Make Number of Distinct Characters Equal - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: Swap 'c' in word1 with 'b' in word2. Result: word1 = "ab" (2 distinct), word2 = "c" (1 distinct). Since 2 ≠ 1, try swapping 'a' with 'b': word1 = "bc" (2 distinct), word2 = "a" (1 distinct). Still not equal. Actually, swapping 'a' with 'b' gives word1 = "bc", word2 = "a", but we need to check all possibilities systematically.

Example 2 — Already Equal

$ Input: word1 = "ab", word2 = "cd"

› Output: false

💡 Note: word1 has 2 distinct characters, word2 has 2 distinct characters. They're already equal, but we need exactly one swap. Any single swap will change the counts, so it's impossible to maintain equality with exactly one move.

Example 3 — Large Difference

$ Input: word1 = "abcc", word2 = "aab"

› Output: true

💡 Note: word1 has 3 distinct characters {a,b,c}, word2 has 2 distinct characters {a,b}. We can swap one 'c' from word1 with 'a' from word2, making both have the same distinct count.

Constraints

1 ≤ word1.length, word2.length ≤ 100
word1 and word2 consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count distinct characters in each string

Swap Simulation

Test character swaps to balance counts

Result

Return true if any swap achieves equality

Key Takeaway

🎯 Key Insight: Use frequency maps to efficiently calculate distinct count changes for each possible character swap

Asked in

M Meta 8 a Amazon 5

The key insight is to calculate how distinct character counts change when swapping characters, without actually reconstructing strings. The frequency count approach is most efficient: Time O(n×m), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Set-Based Optimization	O(d₁×d₂)	O(d₁+d₂)	Use sets to avoid duplicate character checks and reduce redundant operations
Brute Force - Try All Swaps	O(n×m×(n+m))	O(1)	Try every possible character swap and check if distinct counts become equal
Frequency Count Optimization	O(n×m)	O(1)	Use character frequency maps to efficiently check swap effects

Set-Based Optimization — Algorithm Steps

Create sets of unique characters in both strings
For each unique character pair, calculate swap effects
Use set operations to determine distinct count changes
Return true if any swap equalizes the counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Unique Characters

Get sets of distinct characters

Test Unique Pairs

Only check unique character combinations

Calculate Changes

Compute distinct count changes efficiently

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(const char* word1, const char* word2) {
    int freq1[256] = {0};
    int freq2[256] = {0};
    bool chars1[256] = {false};
    bool chars2[256] = {false};
    int n1 = strlen(word1), n2 = strlen(word2);
    
    for (int i = 0; i < n1; i++) {
        freq1[(unsigned char)word1[i]]++;
        chars1[(unsigned char)word1[i]] = true;
    }
    for (int i = 0; i < n2; i++) {
        freq2[(unsigned char)word2[i]]++;
        chars2[(unsigned char)word2[i]] = true;
    }
    
    int distinct1 = 0, distinct2 = 0;
    for (int i = 0; i < 256; i++) {
        if (freq1[i] > 0) distinct1++;
        if (freq2[i] > 0) distinct2++;
    }
    
    for (int i = 0; i < 256; i++) {
        if (!chars1[i]) continue;
        for (int j = 0; j < 256; j++) {
            if (!chars2[j]) continue;
            
            int newDistinct1 = distinct1;
            int newDistinct2 = distinct2;
            
            // Effect of removing char i from word1
            if (freq1[i] == 1) {
                newDistinct1--;
            }
            
            // Effect of adding char j to word1
            if (freq1[j] == 0) {
                newDistinct1++;
            }
            
            // Effect of removing char j from word2
            if (freq2[j] == 1) {
                newDistinct2--;
            }
            
            // Effect of adding char i to word2
            if (freq2[i] == 0) {
                newDistinct2++;
            }
            
            if (newDistinct1 == newDistinct2) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    char word1[1001], word2[1001];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    
    // Remove newlines
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    bool result = solution(word1, word2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d₁×d₂)

d₁ and d₂ are distinct character counts, which is better than n×m when strings have duplicates

✓ Linear Growth

Space Complexity

O(d₁+d₂)

Sets store distinct characters from both strings

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Set-Based Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler