LeetCode 2531: Make Number of Distinct Characters Equal
Problem Description
Explanation:
To determine if it is possible to make the number of distinct characters in word1 and word2 equal with exactly one move, we need to consider the following cases:
- If the total number of distinct characters in both strings is already equal, return true.
- If the difference between the number of distinct characters in
word1andword2is more than 1, return false. - If the difference is exactly 1, we can achieve the goal with one swap.
Algorithm:
- Count the occurrences of each character in
word1andword2. - Calculate the number of distinct characters in
word1andword2. - If the number of distinct characters in both strings is the same, return true.
- If the difference is more than 1, return false.
- If the difference is exactly 1, check if one of the strings contains a character that is not present in the other string. If found, return true; otherwise, return false.
Time Complexity: O(n) Space Complexity: O(1)
:
Solutions
class Solution {
public boolean makeEqual(String word1, String word2) {
int[] count1 = new int[26];
int[] count2 = new int[26];
for (char c : word1.toCharArray()) {
count1[c - 'a']++;
}
for (char c : word2.toCharArray()) {
count2[c - 'a']++;
}
int distinct1 = 0, distinct2 = 0;
for (int count : count1) {
if (count > 0) distinct1++;
}
for (int count : count2) {
if (count > 0) distinct2++;
}
if (distinct1 == distinct2) {
return true;
}
if (Math.abs(distinct1 - distinct2) > 1) {
return false;
}
if (distinct1 > distinct2) {
return checkDistinct(count1, count2);
} else {
return checkDistinct(count2, count1);
}
}
private boolean checkDistinct(int[] count1, int[] count2) {
for (int i = 0; i < 26; i++) {
if (count1[i] > 0 && count2[i] == 0) {
return true;
}
}
return false;
}
}Loading editor...