2531. Make Number of Distinct Characters Equal

MediumHash TableStringCounting
Leetcode Link

Problem Description

In this problem, we are given two zero-indexed (meaning indexing starts from 0) strings word1 and word2. We are allowed to perform a move which involves choosing two indices i from word1 and j from word2 (both indices must be within the bounds of their respective strings) and swapping the characters at these positions, i.e., word1[i] and word2[j].

The objective is to determine if it is possible to equalize the number of distinct characters in both word1 and word2 using exactly one such move. If this is possible, our function should return true. Otherwise, it should return false.

Intuition

The intuition behind the solution is based on counting characters in each string and then considering every possible swap to see if it can lead us to the goal of equalizing the distinct number of characters in both strings with just one move.

To keep track of the characters, we use two arrays cnt1 and cnt2 of size 26 (assuming the input strings consist of lowercase alphabetic characters only). Each array corresponds to counting occurrences of characters in word1 and word2, respectively.

Here's the thinking process to arrive at the solution:

  • We first count how many times each character appears in both word1 and word2.
  • Then, we iterate through the counts of both cnt1 and cnt2. For every pair of characters (i, j) where cnt1[i] and cnt2[j] are both non-zero (indicating that character i is available to swap in word1 and character j in word2), we emulate a swap.
  • After the virtual swap, we calculate the number of distinct characters currently present in cnt1 and cnt2.
  • We check if the number of distinct characters is now equal in both. If it is, we return true.
  • If it isn't, we revert the swap back to its original state and continue with the next possible swap pair.

The reason we try every possible swap is that the distinct number of characters is influenced by both the characters being swapped in and out. So, to find out if any swap can achieve our goal, we have to examine each possibility.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The implementation of the solution follows a simple yet efficient brute-force approach to verify whether a single swap can make the number of distinct characters equal in both strings. Here's a walk-through:

  • Data Structures: Two arrays cnt1 and cnt2 are utilized, each with a length of 26 corresponding to the 26 letters in the English alphabet. These arrays are used to count the occurrences of each character in word1 and word2 respectively.

  • Counting Characters: Iterate over word1 and word2 to count each character. This is done by converting the character to its ASCII value with ord(c), subtracting the ASCII value of 'a' to normalize the index to 0-25, and incrementing the count at that index in cnt1 or cnt2. This looks like the following:

    1for c in word1:
2    cnt1[ord(c) - ord('a')] += 1
3for c in word2:
4    cnt2[ord(c) - ord('a')] += 1

  • Attempting Swaps: The next step is to consider every possible swap. For this, nested loops are used to go over every index i in cnt1 and every index j in cnt2. If cnt1[i] and cnt2[j] are both greater than 0 (meaning both characters are present in their respective strings), a virtual swap is performed:

    1cnt1[i], cnt2[j] = cnt1[i] - 1, cnt2[j] - 1
2cnt1[j], cnt2[i] = cnt1[j] + 1, cnt2[i] + 1

    This emulates moving one occurrence of the i-th character from word1 to word2 and one occurrence of the j-th character from word2 to word1.

  • Checking Distinct Characters: After emulating the swap, a check is performed to determine if the number of distinct characters in both arrays is the same. This is done by summing up the count of indices greater than 0 in both arrays:

    1if sum(v > 0 for v in cnt1) == sum(v > 0 for v in cnt2):
2    return True

  • Reverting Swap: If the numbers are not equal, the swap is reverted:

    1cnt1[i], cnt2[j] = cnt1[i] + 1, cnt2[j] + 1
2cnt1[j], cnt2[i] = cnt1[j] - 1, cnt2[i] - 1

    And the algorithm continues to the next possible swap.

  • Result: If a successful swap that balances the number of distinct characters is found, the function returns True. If no such swap is found after all possibilities have been considered, the function eventually returns False.

This algorithm is efficient in the sense that it goes through a limited set of possible swaps (at most 26 * 26) and requires no extra space besides the two counting arrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have word1 = "abc" and word2 = "def". Our goal is to determine if we can equalize the number of distinct characters in both words by performing exactly one swap.

First, we initialize two arrays to count the occurrences of each character, cnt1 and cnt2. After iterating through each word:

cnt1 (for word1) would be [1, 1, 1, 0, 0, 0, ..., 0] corresponding to [a, b, c, ..., z]. cnt2 (for word2) would be [0, 0, 0, 1, 1, 1, ..., 0] also corresponding to [a, b, c, ..., z].

Now, we attempt every possible swap between characters in word1 and word2:

1. Trying to swap a from word1 with d from word2

We adjust our count arrays to reflect this potential swap:

  • cnt1 becomes [0, 1, 1, 1, 0, 0, ..., 0]
  • cnt2 becomes [1, 0, 0, 0, 1, 1, ..., 0]

We now check if the number of distinct characters in both is the same:

  • cnt1 has 3 distinct characters (b, c, d)
  • cnt2 has 3 distinct characters (a, e, f)

Since the number of distinct characters is equal, we return True.

However, if we need to continue to illustrate the rest of the process, we would revert this virtual swap and try other possibilities:

Revert back to original counts:

  • cnt1 becomes [1, 1, 1, 0, 0, 0, ..., 0]
  • cnt2 becomes [0, 0, 0, 1, 1, 1, ..., 0]

2. Trying to swap a from word1 with e from word2

... and so on for every character in word1 vs every character in word2.

For the sake of this example, we already found a swap that works, so there's no need to continue. The function would now return True. If a swap could not equalize the number of distinct characters, then we would finally return False after exhausting all the combinations.

Solution Implementation

1class Solution:
2    def isItPossible(self, word1: str, word2: str) -> bool:
3        # Count the frequency of each character in both words
4        count1 = [0] * 26
5        count2 = [0] * 26
6      
7        # Update the character frequency for word1
8        for char in word1:
9            count1[ord(char) - ord('a')] += 1
10      
11        # Update the character frequency for word2
12        for char in word2:
13            count2[ord(char) - ord('a')] += 1
14      
15        # Try swapping frequencies and check if both words can have the same character set
16        for i, frequency1 in enumerate(count1):
17            for j, frequency2 in enumerate(count2):
18                # Only proceed with the swap if both frequencies are non-zero
19                if frequency1 and frequency2:
20                    # Decrement and increment the frequencies at position i and j respectively
21                    count1[i], count2[j] = count1[i] - 1, count2[j] - 1
22                    count1[j], count2[i] = count1[j] + 1, count2[i] + 1
23                  
24                    # Calculate the number of distinct characters current in each word
25                    distinct_in_word1 = sum(v > 0 for v in count1)
26                    distinct_in_word2 = sum(v > 0 for v in count2)
27                  
28                    # If both words have the same number of distinct characters, return True
29                    if distinct_in_word1 == distinct_in_word2:
30                        return True
31                  
32                    # Revert the changes if the above condition is not met
33                    count1[i], count2[j] = count1[i] + 1, count2[j] + 1
34                    count1[j], count2[i] = count1[j] - 1, count2[i] - 1
35      
36        # If no swaps can result in both words having the same character set, return False
37        return False
38
1class Solution {
2    public boolean isItPossible(String word1, String word2) {
3        // Create arrays to count the frequency of each character in both strings
4        int[] countWord1 = new int[26];
5        int[] countWord2 = new int[26];
6      
7        // Count the frequency of each character in word1
8        for (int i = 0; i < word1.length(); ++i) {
9            countWord1[word1.charAt(i) - 'a']++;
10        }
11      
12        // Count the frequency of each character in word2
13        for (int i = 0; i < word2.length(); ++i) {
14            countWord2[word2.charAt(i) - 'a']++;
15        }
16      
17        // Iterate over all pairs of characters
18        for (int i = 0; i < 26; ++i) {
19            for (int j = 0; j < 26; ++j) {
20                // If both characters are present in their respective words
21                if (countWord1[i] > 0 && countWord2[j] > 0) {
22                    // Simulate swapping the characters
23                    countWord1[i]--;
24                    countWord2[j]--;
25                    countWord1[j]++;
26                    countWord2[i]++;
27                  
28                    // Check if the frequency distribution matches after the swap
29                    int delta = 0; // Delta will store the net difference in frequencies
30                    for (int k = 0; k < 26; ++k) {
31                        if (countWord1[k] > 0) {
32                            delta++;
33                        }
34                        if (countWord2[k] > 0) {
35                            delta--;
36                        }
37                    }
38                  
39                    // If delta is zero, it means that the frequency distribution matches
40                    if (delta == 0) {
41                        return true;
42                    }
43                  
44                    // Undo the swap operation as it did not lead to a match
45                    countWord1[i]++;
46                    countWord2[j]++;
47                    countWord1[j]--;
48                    countWord2[i]--;
49                }
50            }
51        }
52      
53        // If no swaps resulted in a match, return false
54        return false;
55    }
56}
57
1#include <string>
2
3class Solution {
4public:
5    bool isItPossible(std::string word1, std::string word2) {
6        // Arrays to store letter frequencies for both words
7        int count1[26] = {0};
8        int count2[26] = {0};
9      
10        // Populate frequency arrays for word1
11        for (char c : word1) {
12            ++count1[c - 'a'];
13        }
14      
15        // Populate frequency arrays for word2
16        for (char c : word2) {
17            ++count2[c - 'a'];
18        }
19      
20        // Iterate over each letter in the alphabet
21        for (int i = 0; i < 26; ++i) {
22            // Iterate over each letter in the alphabet
23            for (int j = 0; j < 26; ++j) {
24                // Check if current letters are present in both words
25                if (count1[i] > 0 && count2[j] > 0) {
26                    // Simulate swapping the letters by updating counts
27                    --count1[i];
28                    --count2[j];
29                    ++count1[j];
30                    ++count2[i];
31                  
32                    // Variable to track the sum of differences in frequencies
33                    int difference = 0;
34                    // Check if the frequencies match for each letter
35                    for (int k = 0; k < 26; ++k) {
36                        if (count1[k] > 0) {
37                            ++difference;
38                        }
39                        if (count2[k] > 0) {
40                            --difference;
41                        }
42                    }
43                  
44                    // If the sum of differences is zero, words can be made identical
45                    if (difference == 0) {
46                        return true;
47                    }
48                  
49                    // Undo the simulated swap
50                    ++count1[i];
51                    ++count2[j];
52                    --count1[j];
53                    --count2[i];
54                }
55            }
56        }
57      
58        // If no swap can make the words identical, return false
59        return false;
60    }
61};
62
1function isItPossible(word1: string, word2: string): boolean {
2    // Arrays to store letter frequencies for both words
3    let count1: number[] = new Array(26).fill(0);
4    let count2: number[] = new Array(26).fill(0);
5
6    // Populate frequency arrays for word1
7    for (let c of word1) {
8        count1[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
9    }
10
11    // Populate frequency arrays for word2
12    for (let c of word2) {
13        count2[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
14    }
15
16    // Iterate over each letter in the alphabet
17    for (let i = 0; i < 26; ++i) {
18        // Iterate over each letter in the alphabet
19        for (let j = 0; j < 26; ++j) {
20            // Check if current letters are present in both words
21            if (count1[i] > 0 && count2[j] > 0) {
22                // Simulate swapping the letters by updating counts
23                count1[i]--;
24                count2[j]--;
25                count1[j]++;
26                count2[i]++;
27
28                // Variable to track the sum of differences in frequencies
29                let difference = 0;
30                // Check if the frequencies match for each letter
31                for (let k = 0; k < 26; ++k) {
32                    if (count1[k] > 0) {
33                        difference++;
34                    }
35                    if (count2[k] > 0) {
36                        difference--;
37                    }
38                }
39
40                // If the sum of differences is zero, words can be made identical
41                if (difference === 0) {
42                    return true;
43                }
44
45                // Undo the simulated swap
46                count1[i]++;
47                count2[j]++;
48                count1[j]--;
49                count2[i]--;
50            }
51        }
52    }
53
54    // If no swap can make the words identical, return false
55    return false;
56}
57
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The provided code iterates over each character in word1 and word2, counting the frequency of every character. Then it has nested loops where it iterates over the counts of characters in cnt1 and cnt2 arrays (size 26 for each letter of the alphabet) and performs operations to check if swapping characters could make the frequency of non-zero characters in the count arrays equal.

The time complexity of counting characters is O(n) for each word, where n is the length of the word. However, the nested loops create a bigger time complexity issue. There are 26 possible characters, leading to 26*26 comparisons in the worst case which, is O(26^2) or simply O(1) since 26 is a constant and does not change with the input size.

Combining these, the overall time complexity is primarily affected by the character counting, so O(n) for word1 plus O(m) for word2, where n and m are the lengths of word1 and word2 respectively. Since the 26*26 operations are constant time and do not scale with n or m, the insignificant additional constant time doesn't affect the overall complexity.

The total time complexity is O(n + m), where n is the length of word1 and m is the length of word2.

Space Complexity

The space complexity is much simpler to analyze. The space required by the algorithm is the space for the two count arrays cnt1 and cnt2 which hold the frequency of each character. As these arrays have a fixed size of 26, regardless of the input size, the space complexity is O(1).

Putting it all together, the space complexity is O(1) because it only requires fixed space for the frequency counts and a few variables for iteration and comparison, which does not scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫