Frequency array: Example on strings
We are given two lowercase strings and . We need to check whether we can rearrange the letters of and get .
In other words, both strings must contain the same letters with the same frequencies.
Examples:
Instead of matching characters one by one, we count them. For each lowercase character , we convert it into an index from to :
So:
We build one frequency array for and another frequency array for . After that, we compare all positions. The important idea is:
Two lowercase strings can be rearranged into each other exactly when every letter has the same frequency in both strings.
So we do not care where the letters stand. We only care how many times each letter appears.
First, if the lengths of the strings are different, the answer is immediately NO. A rearrangement cannot change the length.
Then we count characters in both strings. For every character in , we increase its count in . For every character in , we increase its count in .
Finally, we compare the two frequency arrays. If some letter has different counts, the answer is NO. If all counts are equal, the answer is YES.
Algorithm:
int id = ch - 'a';
1. Read strings s and t.
2. If their lengths are different:
2.1. Print NO.
2.2. Stop.
3. Create cnt_s[0..25] and cnt_t[0..25], filled with zeroes.
4. For each character ch in s:
4.1. id = ch - 'a'.
4.2. Increase cnt_s[id] by 1.
5. For each character ch in t:
5.1. id = ch - 'a'.
5.2. Increase cnt_t[id] by 1.
6. For id = 0 to 25:
6.1. If cnt_s[id] != cnt_t[id], print NO and stop.
7. Print YES.
#include <bits/stdc++.h>
using namespace std;
const int K = 26;
string s, t;
int cnt_s[K];
int cnt_t[K];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> t;
if (s.size() != t.size()) {
cout << "NO\n";
return 0;
}
for (char ch : s) {
cnt_s[ch - 'a']++;
}
for (char ch : t) {
cnt_t[ch - 'a']++;
}
for (int i = 0; i < K; i++) {
if (cnt_s[i] != cnt_t[i]) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}