หาจำนวนการเปลี่ยนแปลงน้อยที่สุดเพื่อทำให้สตริงสองสตริงเป็น Anagram โดยไม่ลบตัวอักษร ใน C++

บทนำ

กำหนดสตริงสองสตริงที่มีความยาวเท่ากัน ต้องการหาจำนวนการเปลี่ยนแปลง (alterations) น้อยที่สุด เพื่อทำให้ทั้งสองเป็น Anagram (มีชุดตัวอักษรเหมือนกัน) โดยไม่ลบตัวอักษรใดๆ

ตัวอย่าง: "HELLO" และ "WORLD" → ต้องเปลี่ยน 3 ตัวอักษร

แนวคิด

1. นับความถี่ (frequency) ของแต่ละตัวอักษรในสตริงแรก
2. วนลูปสตริงที่สอง ถ้าตัวอักษรมีใน frequency array ให้ลดค่าลง 1
3. ถ้าค่า frequency ติดลบ (< 0) ให้เพิ่มนับจำนวนการเปลี่ยนแปลง

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

#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 << "Number of required alteration: " << countAlteration(s1, s2);
    return 0;
}

ผลลัพธ์

Number of required alteration: 3