สมมติว่าเรามีสตริงสองสายที่มีความยาวเท่ากัน เราต้องหาจำนวนการเปลี่ยนแปลงขั้นต่ำที่จำเป็นในการสร้างแอนนาแกรมสองสตริง โดยไม่ลบอักขระใดๆ แอนนาแกรมเป็นสองสตริงที่มีชุดอักขระเหมือนกัน สมมติว่าสตริงสองสตริงคือ "HELLO" และ "WORLD" ในที่นี้ จำนวนการเปลี่ยนแปลงที่จำเป็นคือ 3 เนื่องจากอักขระ 3 ตัวจะแตกต่างกันในกรณีนี้
แนวคิดนี้ง่ายมาก เราต้องหาความถี่ของอักขระแต่ละตัวในสตริงแรก จากนั้นจึงไปที่สตริงที่สอง หากมีอักขระในสตริงที่สอง ในอาร์เรย์ความถี่ ให้ลดค่าความถี่ลง หากค่าความถี่น้อยกว่า 0 ให้เพิ่มจำนวนสุดท้ายขึ้น 1
ตัวอย่าง
#include <iostream>
using namespace std;
int countAlteration(string str1, string str2) {
int count = 0;
int frequency[26];
for (int i = 0; i < 26; i++){
frequency[i] = 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);
} ผลลัพธ์
Number of required alteration: 3
