Minimum Number of Steps to Make Two Strings Anagram ใน C++

ให้ String s และ t ความยาวเท่ากัน ใน 1 Step เลือก Char ใน t 1 ตัว แทนที่ด้วย Char อื่น หา **Steps น้อยที่สุด** ทำให้ t เป็น **Anagram** ของ s (มีตัวอักษรชนิดและจำนวนเท่ากัน ไม่สนลำดับ)

ตัวอย่าง

s = "yxy", t = "xyx"

s Count: x:1, y:2 | t Count: x:2, y:1

ต้องเปลี่ยน 'x' 1 ตัวใน t เป็น 'y' -> 1 Step

แนวทาง: Frequency Count + Match Common Characters

1. Count Frequency ของแต่ละ Char ใน s (countS) และ t (countT)
2. สำหรับแต่ละ Char c: จำนวนที่ **Match ได้** = min(countS[c], countT[c])
3. Total Matched = Sum ของ Matched ทุก Char
4. Steps = n - TotalMatched (ตัวที่ไม่ Match ต้องเปลี่ยน)

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

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

class Solution {
public:
    int minSteps(string s, string t) {
        int n = s.size();
        vector<int> countS(26, 0), countT(26, 0);

        for (char c : s) countS[c - 'a']++;
        for (char c : t) countT[c - 'a']++;

        int matched = 0;
        for (int i = 0; i < 26; i++) {
            matched += min(countS[i], countT[i]);
        }
        return n - matched;
    }
};

Input / Output

Input:  "yxy" "xyx"
Output: 1

ความซับซ้อน (Complexity)

• Time: O(N) — Count Frequencies + 26 Loop
• Space: O(1) — 2 Arrays ขนาด 26

Intuition

Anagram = Same Multiset of Characters. จำนวน Char ที่ "อยู่แล้วถูกต้อง" = Min(Count in S, Count in T) ส่วนที่เกิน/ขาด ต้อง Swap/Replace ครบครับ