[LeetCode] Make Number of Distinct Characters Equal

2531. 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
bool check(vector<int>& A, vector<int>& B) {
int cnt = 0;
for(int i = 0; i < 26; i++) {
if(A[i]) cnt += 1;
if(B[i]) cnt -= 1;
}
return cnt == 0;
}
public:
bool isItPossible(string word1, string word2) {
vector<int> freq1(26), freq2(26);
for(auto w : word1) freq1[w-'a'] += 1;
for(auto w : word2) freq2[w-'a'] += 1;
for(int i = 0; i < 26; i++) {
if(!freq1[i]) continue;
for(int j = 0; j < 26; j++) {
if(!freq2[j]) continue;
freq1[i] -= 1;
freq2[j] -= 1;
freq1[j] += 1;
freq2[i] += 1;
if(check(freq1,freq2)) return true;
freq1[i] += 1;
freq2[j] += 1;
freq1[j] -= 1;
freq2[i] -= 1;
}
}
return false;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/02/07/PS/LeetCode/make-number-of-distinct-characters-equal/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.