Minimum String in C++: หาจำนวนการเปลี่ยนแปลงน้อยที่สุดเพื่อทำให้ String เหมือนกัน

กำหนดให้มีสตริงสองตัว s และ t ที่มีความยาวเท่ากันและประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กทั้งหมด เราสามารถจัดเรียง s ใหม่ได้ตามต้องการ จากนั้นนับจำนวนการเปลี่ยนแปลงตัวอักษรขั้นต่ำเพื่อให้ s กลายเป็น t

ตัวอย่าง: s = "eccynue", t = "science" ผลลัพธ์คือ 2 เพราะจัดเรียง "eccynue" เป็น "yccence" แล้วเปลี่ยน y เป็น s และ c ตัวที่สองเป็น i จะได้ "science"

วิธีแก้ปัญหา

1. นับความถี่ของตัวอักษรแต่ละตัวใน s และ t (ใช้ array ขนาด 26)
2. สำหรับตัวอักษรแต่ละตัว คำนวณ max(cnt1[i] - cnt2[i], 0) และรวมกัน
3. ผลรวมนี้คือจำนวนการเปลี่ยนแปลงขั้นต่ำ

ตัวอย่างโค้ด C++

#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(char c : s) cnt1[c - 'a']++;
        for(char c : t) cnt2[c - '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"));
}

Input

"eccynue", "science"

Output

2