2531. Make Number of Distinct Characters Equal LeetCode Solution
In this guide, you will get 2531. Make Number of Distinct Characters Equal LeetCode Solution with the best time and space complexity. The solution to Make Number of Distinct Characters Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Make Number of Distinct Characters Equal
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.
1 <= word1.length, word2.length <= 105
word1 and word2 consist of only lowercase English letters.
Complexity Analysis
Time Complexity: O(26^2 + |\texttt{word1}| + |\texttt{word2}|)
Space Complexity: O(1)
2531. Make Number of Distinct Characters Equal LeetCode Solution in C++
class Solution {
public:
bool isItPossible(string word1, string word2) {
const vector<int> count1 = getCount(word1);
const vector<int> count2 = getCount(word2);
const int distinct1 = getDistinct(count1);
const int distinct2 = getDistinct(count2);
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j) {
if (count1[i] == 0 || count2[j] == 0)
continue;
if (i == j) {
// Swapping the same letters won't change the number of distinct
// letters in each string, so just check if `distinct1 == distinct2`.
if (distinct1 == distinct2)
return true;
continue;
}
// The calculation is meaningful only when i != j.
// Swap ('a' + i) in word1 with ('a' + j) in word2.
const int distinctAfterSwap1 =
distinct1 - (count1[i] == 1) + (count1[j] == 0);
const int distinctAfterSwap2 =
distinct2 - (count2[j] == 1) + (count2[i] == 0);
if (distinctAfterSwap1 == distinctAfterSwap2)
return true;
}
return false;
}
private:
vector<int> getCount(const string& s) {
vector<int> count(26);
for (const char c : s)
++count[c - 'a'];
return count;
}
int getDistinct(const vector<int>& count) {
return ranges::count_if(count, [](const int c) { return c > 0; });
}
}; /* code provided by PROGIEZ */
2531. Make Number of Distinct Characters Equal LeetCode Solution in Java
class Solution {
public boolean isItPossible(String word1, String word2) {
final int[] count1 = getCount(word1);
final int[] count2 = getCount(word2);
final int distinct1 = getDistinct(count1);
final int distinct2 = getDistinct(count2);
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j) {
if (count1[i] == 0 || count2[j] == 0)
continue;
if (i == j) {
// Swapping the same letters won't change the number of distinct
// letters in each string, so just check if `distinct1 == distinct2`.
if (distinct1 == distinct2)
return true;
continue;
}
// The calculation is meaningful only when i != j.
// Swap ('a' + i) in word1 with ('a' + j) in word2.
final int distinctAfterSwap1 =
distinct1 - (count1[i] == 1 ? 1 : 0) + (count1[j] == 0 ? 1 : 0);
final int distinctAfterSwap2 =
distinct2 - (count2[j] == 1 ? 1 : 0) + (count2[i] == 0 ? 1 : 0);
if (distinctAfterSwap1 == distinctAfterSwap2)
return true;
}
return false;
}
private int[] getCount(final String s) {
int[] count = new int[26];
for (final char c : s.toCharArray())
++count[c - 'a'];
return count;
}
private int getDistinct(int[] count) {
return (int) Arrays.stream(count).filter(c -> c > 0).count();
}
} // code provided by PROGIEZ
2531. Make Number of Distinct Characters Equal LeetCode Solution in Python
class Solution:
def isItPossible(self, word1: str, word2: str) -> bool:
count1 = collections.Counter(word1)
count2 = collections.Counter(word2)
distinct1 = len(count1)
distinct2 = len(count2)
for a in count1:
for b in count2:
if a == b:
# Swapping the same letters won't change the number of distinct
# letters in each string, so just check if `distinct1 == distinct2`.
if distinct1 == distinct2:
return True
continue
# The calculation is meaningful only when a != b
# Swap a in word1 with b in word2.
distinctAfterSwap1 = distinct1 - (count1[a] == 1) + (count1[b] == 0)
distinctAfterSwap2 = distinct2 - (count2[b] == 1) + (count2[a] == 0)
if distinctAfterSwap1 == distinctAfterSwap2:
return True
return False # code by PROGIEZ
