Số Bước Tối Thiểu Để Làm Cho Hai Chuỗi Trở Thành Anagram Trong C++

Giả sử hai chuỗi s và t cùng độ dài. Trong một bước, chọn bất kỳ ký tự nào của t và thay thế bằng ký tự khác. Tìm số bước tối thiểu để t trở thành anagram của s. Anagram là chuỗi chứa cùng ký tự nhưng thứ tự có thể khác.

Ví dụ: "yxy" và "xyx" → 1 (chỉ cần thay một ký tự).

Để giải quyết, chúng ta làm theo các bước:

• n := độ dài s.

• Tạo map m1 đếm tần suất ký tự trong s, m2 đếm tần suất trong t.

• ret := n.

• Với mỗi cặp khóa-giá trị trong m1: x = min(giá trị, m2[khóa]); ret -= x.

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSteps(string s, string t) {
        int n = s.size();
        map <char, int> m1;
        for(int i = 0; i < s.size(); i++){
            m1[s[i]]++;
        }
        int ret = n;
        map <char, int> m2;
        for(int i = 0; i < t.size(); i++){
            m2[t[i]]++;
        }
        map <char, int> :: iterator it = m1.begin();
        while(it != m1.end()){
            int x = min(it->second, m2[it->first]);
            ret -= x;
            it++;
        }
        return ret;
    }
};

int main(){
    Solution ob;
    cout << (ob.minSteps("yxy", "xyx"));
}

Đầu vào

"yxy" "xyx"

Đầu ra

1