Make Number of Distinct Characters Equal solution and explanation
Google
9 more videos on this problem
Make Number of Distinct Characters Equal | leetcode Weekly 327 | Leetcode MediumBinaryMagic · 13:12 · 1K views
Make Number of Distinct Characters Equal | Leetcode solutions - 2531Algorithms Made Easy · 15:07 · 1K views
Weekly Contest 327 | Make Number of Distinct Characters EqualcodingMohan · 13:54 · 719 views
2531. Make Number of Distinct Characters Equal (Leetcode Medium)Programming Live with Larry · 6:53 · 594 views
Make Number of Distinct Characters Equal | Leetcode 2531 | Leetcode Weekly contest 327Tech Courses · 9:20 · 496 views
C. Make Number of Distinct Characters Equal - LEETCODE WEEKLY CONTEST 327 (Code + Explanation)Joyjit Codes · 5:16 · 318 views
2531 Make Number of Distinct Characters Equal | LeetCode | C++ | Simple ExplanationDeep Tech · 12:09 · 268 views
Make number of Distinct Characters equal | weekly contest 327A Code Daily! · 7:22 · 198 views
2531 Make Number of Distinct Characters Equal Leetcode |Leetcode Weekly Contest 327Ashutosh sharma · 14:58 · 82 views
6284. Make Number of Distinct Characters Equal | Medium | Maps | Weekly Contest 327CodeHub · 8:16 · 69 views
The 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.
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 <= 105word1andword2consist of only lowercase English letters.
Approach overview
Problem Overview: You are given two strings and can swap exactly one character between them. The goal is to determine whether a single swap can make the number of distinct characters in both strings equal.
The challenge is not the swap itself but predicting how the swap changes the distinct counts. Adding a character may increase the distinct set, while removing the last occurrence of a character may decrease it. Efficient solutions track these frequency changes using hash tables or frequency arrays instead of rebuilding sets repeatedly.
Approach 1: Brute Force with Set Operations (O(n * m), space O(26))
Try every possible swap between characters in word1 and word2. For each pair of indices, simulate the swap and compute the number of distinct characters using a set. If both sets end up with the same size, return true. This approach directly models the problem and is easy to reason about, but repeatedly constructing sets makes it inefficient for larger inputs. Still useful as a baseline to validate logic during development.
Approach 2: Optimized Swap Analysis (O(26^2) time, O(26) space)
Instead of trying every position, track character frequencies using arrays or a counting map. Iterate over all possible characters from 'a' to 'z' in both strings. For each potential swap pair, compute how the distinct counts change: removing the last occurrence decreases the count, while introducing a new character increases it. Because the alphabet size is fixed, the search space is only 26 × 26, making this approach effectively constant time.
Set Based Swap Difference Approach (O(26^2) time, O(26) space)
This method maintains two sets representing distinct characters in each string. For each candidate character swap, simulate how the sets would change without modifying the original strings. If the swapped character already exists in the target set, the distinct count stays the same; otherwise it increases. Similarly, removing a character that appears only once reduces the count. This approach focuses directly on distinct set sizes instead of full frequency recalculation.
Count-Based Greedy Check (O(26^2) time, O(26) space)
The most interview-friendly solution uses two frequency arrays and precomputed distinct counts. Iterate through all character pairs that actually appear in the strings. For each pair, compute the resulting distinct counts after the swap using simple arithmetic rules on the frequency values. This avoids rebuilding sets and minimizes branching logic. Because only 26 letters are considered, the runtime remains constant and the implementation is concise.
Recommended for interviews: Start by describing the brute force swap simulation to demonstrate understanding of the problem mechanics. Then move to the frequency-based swap analysis. Interviewers expect the optimized counting approach because it leverages constant alphabet size and avoids rebuilding sets.
Approach 1: Approach 1: Brute Force with Set Operations
This approach systematically attempts all possible character swaps between the two strings and checks if they lead to equal distinct character counts. While this is not optimal, it serves to illustrate the swap process clearly, leveraging set operations to easily compute the distinct character counts.
def can_make_equal(word1, word2):
distinct1 = set(word1)
distinct2 = set(word2)
initial_diff = len(distinct1) - len(distinct2)
for i in range(len(word1)):
for j in range(len(word2)):
# Swap word1[i] with word2[j]
char1, char2 = word1[i], word2[j]
if char1 != char2:
swapped_distinct1 = distinct1.copy()
swapped_distinct2 = distinct2.copy()
# Simulate the swap
if char1 in swapped_distinct1:
swapped_distinct1.remove(char1)
swapped_distinct1.add(char2)
if char2 in swapped_distinct2:
swapped_distinct2.remove(char2)
swapped_distinct2.add(char1)
# Check the equality of distinct char counts
if len(swapped_distinct1) == len(swapped_distinct2):
return True
return FalseThe code iterates over each possible swap between characters of word1 and word2. It uses sets to represent the distinct characters and analyzes the impacts of each swap. It stops and returns true if a swap allows both strings to have equal distinct character counts. Otherwise, it returns false.
Time Complexity: O(n*m) - where n is the length of word1 and m is the length of word2, as we try all possible swaps.
Space Complexity: O(1) - aside from input and sets of size at most 26 (the number of letters in the alphabet).
Approach 2: Approach 2: Optimized Swap Analysis
This optimized approach leverages the observation that only swapping differing characters influences the distinct character count. For efficiency, it utilizes character frequency and state changes per swap to determine whether the swap makes the number of distinct characters equal between the words. This approach carefully tracks when increments and decrements in distinct counts occur and determines equality before actually executing a swap.
import java.util.HashSet;
public class Solution {
public static boolean canMakeEqual(String word1, String word2) {
HashSet<Character> set1 = new HashSet<>();
HashSet<Character> set2 = new HashSet<>();
for (char c : word1.toCharArray()) set1.add(c);
for (char c : word2.toCharArray()) set2.add(c);
int diff = set1.size() - set2.size();
for (int i = 0; i < word1.length(); i++) {
for (int j = 0; j < word2.length(); j++) {
char char1 = word1.charAt(i);
char char2 = word2.charAt(j);
if (char1 != char2) {
int newDiff = diff;
if (set1.contains(char2)) newDiff--;
if (!set1.contains(char1)) newDiff++;
if (set2.contains(char1)) newDiff++;
if (!set2.contains(char2)) newDiff--;
if (newDiff == 0) return true;
}
}
}
return false;
}
}The Java code uses two sets to hold the distinct characters of each string. It goes through each potential swap, evaluating how it would impact the count of distinct characters if it were executed. The key lies in calculating the change in difference in the number of distinct characters and not actually performing the swap, thus reducing computation.
Time Complexity: O(n*m) - though it avoids some redundant computations, making it practically faster.
Space Complexity: O(1) - using sets to track counts only means a space complexity of at most 26 for alphabet characters.
Approach 3: Set Based Swap Difference Approach
Begin by calculating the number of distinct characters in both strings using sets. Iterate over possible characters to swap from both words, and consider how the swapping affects the distinct character counts. To swap effectively, ensure that swapping one character results in a net-zero difference in the count change. This involves leveraging the union-intersection counting of potential new characters.
Check for swap candidates where the removal of one character from a set and addition of another would balance the distinct counts.
def can_swap_to_equal(word1, word2):
word1_set = set(word1)
word2_set = set(word2)
count_diff = len(word1_set) - len(word2_set)
if abs(count_diff) > 1:
return False
for c1 in word1_set:
for c2 in word2_set:
new_word1_set = word1_set.copy()
new_word2_set = word2_set.copy()
new_word1_set.discard(c1)
new_word2_set.discard(c2)
new_word1_set.add(c2)
new_word2_set.add(c1)
if len(new_word1_set) == len(new_word2_set):
return True
return False
# Example Usage:
# print(can_swap_to_equal("abcc", "aab")) # True
# print(can_swap_to_equal("abcde", "fghij")) # True
# print(can_swap_to_equal("ac", "b")) # Falsefunction canSwapToEqual(word1, word2) {
let set1 = new Set(word1);
let set2 = new Set(word2);
let diff = Math.abs(set1.size - set2.size);
if (diff > 1) return false;
for (let char1 of set1) {
for (let char2 of set2) {
let newSet1 = new Set([...set1]);
let newSet2 = new Set([...set2]);
newSet1.delete(char1);
newSet1.add(char2);
newSet2.delete(char2);
newSet2.add(char1);
if (newSet1.size === newSet2.size) {
return true;
}
}
}
return false;
}
// Example Usage:
// console.log(canSwapToEqual("abcc", "aab")); // True
// console.log(canSwapToEqual("abcde", "fghij")); // True
// console.log(canSwapToEqual("ac", "b")); // FalseThis solution makes use of Python sets to store distinct characters from each word. It then evaluates possible swaps of characters between the two sets that result in equal distinct character counts after the swap. The solution ensures the transition maintains the property of distinct character equivalence post-swap.
Time Complexity: O(n * m), where n is the length of word1 and m is the length of word2. For each character combination between the two sets, calculate the effect of swaps.
Space Complexity: O(u + v), where u and v are number of unique characters in word1 and word2, respectively.
Approach 4: Count-Based Greedy Check
Instead of directly iterating over character pairs, attempt to adjust the distinct count via examining count differences directly. Leverage character frequencies and explore scenarios where direct swaps using frequency presence can balance the distinct counts effectively. This avoids exhaustive checks and focuses on potential viable swaps.
import java.util.HashSet;
import java.util.Set;
public class DistinctCharsEqual {
public static boolean canSwapToEqual(String word1, String word2) {
Set<Character> set1 = new HashSet<>();
Set<Character> set2 = new HashSet<>();
for (char c : word1.toCharArray()) set1.add(c);
for (char c : word2.toCharArray()) set2.add(c);
int diff = Math.abs(set1.size() - set2.size());
if (diff > 1) return false;
for (char c1 : set1) {
for (char c2 : set2) {
if (!set1.contains(c2) || !set2.contains(c1)) {
if (set1.size() == set2.size()) return true;
}
}
}
return false;
}
// Example Usage:
// public static void main(String[] args) {
// System.out.println(canSwapToEqual("abcc", "aab")); // true
// System.out.println(canSwapToEqual("abcde", "fghij")); // true
// System.out.println(canSwapToEqual("ac", "b")); // false
// }
}#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#define CHAR_COUNT 26
bool canSwapToEqual(char* word1, char* word2) {
int count1[CHAR_COUNT] = {0};
int count2[CHAR_COUNT] = {0};
for (int i = 0; word1[i] != '\0'; i++)
count1[word1[i] - 'a']++;
for (int i = 0; word2[i] != '\0'; i++)
count2[word2[i] - 'a']++;
int distinct1 = 0, distinct2 = 0;
for (int i = 0; i < CHAR_COUNT; i++) {
if (count1[i] > 0) distinct1++;
if (count2[i] > 0) distinct2++;
}
int diff = abs(distinct1 - distinct2);
if (diff > 1) return false;
for (int i = 0; i < CHAR_COUNT; i++) {
for (int j = 0; j < CHAR_COUNT; j++) {
if ((count1[i] > 0 && count2[j] > 0) &&
((distinct1 - (count1[i] == 1) + (count2[j] == 0)) ==
(distinct2 - (count2[j] == 1) + (count1[i] == 0)))) {
return true;
}
}
}
return false;
}
// Example Usage:
// int main() {
// printf("%d\n", canSwapToEqual("abcc", "aab")); // 1 (true)
// printf("%d\n", canSwapToEqual("abcde", "fghij")); // 1 (true)
// printf("%d\n", canSwapToEqual("ac", "b")); // 0 (false)
// return 0;
// }This Java solution harnesses hash sets to store characters of both words distinctly. It primarily utilizes set operations to determine which unique swaps directly lead to equal distinct character counts. By leveraging the comparison of element existence across sets, viable swap opportunities are quickly identified and validated.
Time Complexity: O(n + m), where n and m are the lengths of word1 and word2. Unlike the iterative pair approach, this method usually operates in a more efficient manner by directly leveraging set operations.
Space Complexity: O(u + v), due to unique character sets required for the solution.
Approach 5: Counting + Enumeration
We first use two arrays cnt1 and cnt2 of length 26 to record the frequency of each character in the strings word1 and word2, respectively.
Then, we count the number of distinct characters in word1 and word2, denoted as x and y respectively.
Next, we enumerate each character c1 in word1 and each character c2 in word2. If c1 = c2, we only need to check if x and y are equal; otherwise, we need to check if x - (cnt1[c1] = 1) + (cnt1[c2] = 0) and y - (cnt2[c2] = 1) + (cnt2[c1] = 0) are equal. If they are equal, then we have found a solution and return true.
If we have enumerated all characters and have not found a suitable solution, we return false.
The time complexity is O(m + n + |\Sigma|^2), where m and n are the lengths of the strings word1 and word2, and \Sigma is the character set. In this problem, the character set consists of lowercase letters, so |\Sigma| = 26.
class Solution {
public:
bool isItPossible(string word1, string word2) {
int cnt1[26]{};
int cnt2[26]{};
int x = 0, y = 0;
for (char& c : word1) {
if (++cnt1[c - 'a'] == 1) {
++x;
}
}
for (char& c : word2) {
if (++cnt2[c - 'a'] == 1) {
++y;
}
}
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (cnt1[i] > 0 && cnt2[j] > 0) {
if (i == j) {
if (x == y) {
return true;
}
} else {
int a = x - (cnt1[i] == 1 ? 1 : 0) + (cnt1[j] == 0 ? 1 : 0);
int b = y - (cnt2[j] == 1 ? 1 : 0) + (cnt2[i] == 0 ? 1 : 0);
if (a == b) {
return true;
}
}
}
}
}
return false;
}
};function isItPossible(word1: string, word2: string): boolean {
const cnt1: number[] = Array(26).fill(0);
const cnt2: number[] = Array(26).fill(0);
let [x, y] = [0, 0];
for (const c of word1) {
if (++cnt1[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
++x;
}
}
for (const c of word2) {
if (++cnt2[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
++y;
}
}
for (let i = 0; i < 26; ++i) {
for (let j = 0; j < 26; ++j) {
if (cnt1[i] > 0 && cnt2[j] > 0) {
if (i === j) {
if (x === y) {
return true;
}
} else {
const a = x - (cnt1[i] === 1 ? 1 : 0) + (cnt1[j] === 0 ? 1 : 0);
const b = y - (cnt2[j] === 1 ? 1 : 0) + (cnt2[i] === 0 ? 1 : 0);
if (a === b) {
return true;
}
}
}
}
}
return false;
}func isItPossible(word1 string, word2 string) bool {
cnt1 := [26]int{}
cnt2 := [26]int{}
x, y := 0, 0
for _, c := range word1 {
cnt1[c-'a']++
if cnt1[c-'a'] == 1 {
x++
}
}
for _, c := range word2 {
cnt2[c-'a']++
if cnt2[c-'a'] == 1 {
y++
}
}
for i := range cnt1 {
for j := range cnt2 {
if cnt1[i] > 0 && cnt2[j] > 0 {
if i == j {
if x == y {
return true
}
} else {
a := x
if cnt1[i] == 1 {
a--
}
if cnt1[j] == 0 {
a++
}
b := y
if cnt2[j] == 1 {
b--
}
if cnt2[i] == 0 {
b++
}
if a == b {
return true
}
}
}
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Set Operations | Time Complexity: O(n*m) - where n is the length of |
| Approach 2: Optimized Swap Analysis | Time Complexity: O(n*m) - though it avoids some redundant computations, making it practically faster. |
| Set Based Swap Difference Approach | Time Complexity: O(n * m), where n is the length of |
| Count-Based Greedy Check | Time Complexity: O(n + m), where n and m are the lengths of word1 and word2. Unlike the iterative pair approach, this method usually operates in a more efficient manner by directly leveraging set operations. |
| Counting + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set Operations | O(n * m) | O(26) | Simple baseline implementation or for validating logic |
| Optimized Swap Analysis | O(26^2) | O(26) | General optimal solution using frequency arrays |
| Set Based Swap Difference | O(26^2) | O(26) | When reasoning about distinct characters directly using sets |
| Count-Based Greedy Check | O(26^2) | O(26) | Interview-preferred solution with minimal operations |
Frequently asked questions
Is Make Number of Distinct Characters Equal easy or hard?
Make Number of Distinct Characters Equal is considered a Medium difficulty problem on LeetCode. The difficulty comes from reasoning about how swapping characters changes distinct counts rather than from implementing complex algorithms.
Make Number of Distinct Characters Equal Python/Java solution
Python solutions typically use dictionaries or collections.Counter to store character frequencies and simulate swaps. Java implementations often rely on integer arrays of size 26 to track counts and compute distinct character changes efficiently.
How to solve Make Number of Distinct Characters Equal in O(n)?
First count the frequency of each character in both strings using hash maps or arrays. Then iterate through all possible character swaps and compute how each swap changes the distinct counts using the stored frequencies. The counting step takes O(n), and the swap analysis runs in O(26^2), giving near-linear overall complexity.
What is the best approach for Make Number of Distinct Characters Equal?
The best approach uses frequency counting and analyzes how a swap affects distinct character counts. By storing counts for both strings and checking all possible character pairs from 'a' to 'z', you can simulate the effect of a swap without rebuilding the strings. This runs in O(26^2) time and O(26) space, which is effectively constant.
Is Make Number of Distinct Characters Equal asked at Google/Amazon/Meta?
Problems involving string frequency manipulation and hash table counting are common in interviews at companies like Amazon, Google, and Meta. Variations of this problem appear in interview rounds that test reasoning about character counts, hash maps, and edge-case handling.
What data structure is used in Make Number of Distinct Characters Equal?
The core data structures are hash tables or fixed-size frequency arrays for counting characters. Sets may also be used to track distinct characters, but frequency arrays are more efficient because they allow quick updates when simulating swaps.
What is the time complexity of Make Number of Distinct Characters Equal?
The optimal solution runs in O(26^2) time because it checks every possible pair of characters from the lowercase alphabet. Since the alphabet size is fixed, the complexity behaves like constant time in practice. Space complexity is O(26) for storing frequency counts.