Chuỗi nhỏ nhất trong C++

Giả sử chúng ta có hai chuỗi s và t cùng độ dài, đều chỉ chứa chữ cái thường. Ta sắp xếp lại s theo bất kỳ thứ tự nào, sau đó đếm số lần thay đổi ký tự tối thiểu để biến s thành t.

Ví dụ, với s = "eccynue", t = "science", kết quả là 2. Nếu sắp xếp "eccynue" thành "yccence", sau đó thay 'y' bằng 's' và 'c' thứ hai bằng 'i', ta được "science".

Các bước giải quyết:

• Khởi tạo ret := 0.
• Tạo hai mảng cnt1 và cnt2 lưu tần suất ký tự của s và t.
• Duyệt i từ 0 đến 25: ret := ret + max(cnt1[i] - cnt2[i], 0).
• Trả về ret.

Ví dụ

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

class Solution {
public:
    int solve(string s, string t) {
        int ret = 0;
        vector<int> cnt1(26), cnt2(26);
        for (int i = 0; i < s.size(); i++)
            cnt1[s[i] - 'a']++;
        for (int i = 0; i < t.size(); i++)
            cnt2[t[i] - 'a']++;
        for (int i = 0; i < 26; i++)
            ret += max(cnt1[i] - cnt2[i], 0);
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.solve("eccynue", "science"));
}

Đầu vào

"eccynue", "science"

Đầu ra

2