Cho hai chuỗi str1 và str2, đếm số cặp ký tự chung (str1[i] == str2[j]) - mỗi ký tự trong str1 chỉ ghép với một ký tự giống trong str2 (xét tần suất).
Ví dụ
Input - str1 = "hello", str2 = "heoo" Output - count: 3
Giải thích - h, e, o (str1 có 2 'l' nhưng str2 không có 'l'; str2 có 2 'o' nhưng str1 chỉ có 1 'o') → min(freq) cho từng ký tự.
Input - str1 = "point", str2 = "print" Output - count: 4
Giải thích - p, i, n, t chung (o vs r khác).
Phương pháp tiếp cận (Tần suất)
- Tính tần suất f1[26] cho str1, f2[26] cho str2 (chỉ a-z)
- Tổng count = Σ min(f1[i], f2[i]) với i=0..25
Ví dụ code C++
#include <iostream>
#include <string>
using namespace std;
int pairs(string str1, int size1, string str2, int size2) {
int f1[26] = {0}, f2[26] = {0};
for (int i = 0; i < size1; i++) f1[str1[i] - 'a']++;
for (int i = 0; i < size2; i++) f2[str2[i] - 'a']++;
int c = 0;
for (int i = 0; i < 26; i++)
c += min(f1[i], f2[i]);
return c;
}
int main() {
string str1 = "tutorialspoint", str2 = "codingground";
int size1 = str1.length(), size2 = str2.length();
cout << "Total common pairs: " << pairs(str1, size1, str2, size2);
return 0;
}
Kết quả
Total common pairs: 6