Số thao tác tối thiểu để hai chuỗi thành anagram mà không xóa ký tự trong C++

Cho hai chuỗi cùng độ dài, tìm số lần thay đổi ký tự tối thiểu để chúng trở thành anagram (cùng tập ký tự) mà không xóa ký tự nào. Ví dụ: "HELLO" và "WORLD" cần 3 thay đổi.

Ý tưởng: đếm tần suất ký tự chuỗi thứ nhất, duyệt chuỗi thứ hai, nếu ký tự có trong mảng tần suất thì giảm đếm. Nếu đếm âm thì tăng số thay đổi.

Ví dụ minh họa

#include <iostream>
using namespace std;

int countAlteration(string str1, string str2) {
    int count = 0;
    int frequency[26] = {0};
    for (int i = 0; i < str1.length(); i++)
        frequency[str1[i] - 'A']++;
    for (int i = 0; i < str2.length(); i++) {
        frequency[str2[i] - 'A']--;
        if (frequency[str2[i] - 'A'] < 0)
            count++;
    }
    return count;
}

int main() {
    string s1 = "HELLO", s2 = "WORLD";
    cout << "So thay doi can thiet: " << countAlteration(s1, s2);
    return 0;
}

Kết quả

So thay doi can thiet: 3