Permutation in String ใน C++

โจทย์: Permutation in String

ให้สตริงสองตัว s1 และ s2 ต้องตรวจสอบว่า s2 มี substring ที่เป็น permutation (การจัดเรียงใหม่) ของ s1 หรือไม่ นั่นคือ ตัวอักษรของ s1 สามารถเรียงใหม่ได้เป็น substring ติดต่อกันใน s2

ตัวอย่าง: s1 = "abc", s2 = "findcab"

Permutation ของ "abc" คือ "cab" ซึ่งเป็น substring ของ "findcab" → true

อัลกอริทึม: Sliding Window + Character Count

1. นับความถี่ตัวอักษรใน s1 → cnt1[26]
2. ใช้ sliding window ขนาด len(s1) บน s2 นับความถี่ใน window → cnt2[26]
3. เลื่อน window ทีละตัว อัปเดต cnt2 (เพิ่มตัวใหม่ ลบตัวเก่า)
4. ที่แต่ละตำแหน่ง ตรวจสอบ cnt1 == cnt2 หากใช่ → true
5. จบลูป → false

Optimization: แทนที่จะเปรียบเทียบ array 26 ตัวทุกครั้ง ใช้ตัวแปร matches นับจำนวนตัวอักษรที่ cnt1[c] == cnt2[c] เมื่อ matches == 26 → match

ตัวอย่างโค้ด C++ (Sliding Window แบบปกติ)

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

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) return false;
        
        vector<int> cnt1(26, 0), cnt2(26, 0);
        for (char c : s1) cnt1[c - 'a']++;
        
        int window_size = s1.size();
        
        // Initialize first window
        for (int i = 0; i < window_size; i++)
            cnt2[s2[i] - 'a']++;
        if (cnt1 == cnt2) return true;
        
        // Slide window
        for (int i = window_size; i < s2.size(); i++) {
            cnt2[s2[i] - 'a']++;                    // เพิ่มตัวใหม่
            cnt2[s2[i - window_size] - 'a']--;      // ลบตัวเก่า
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    cout << (ob.checkInclusion("abc", "findcab") ? "true" : "false") << endl;
    return 0;
}

Input

"abc" "findcab"

Output

true

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

• เวลา: O(n + m) โดย n = |s1|, m = |s2| (เปรียบเทียบ array 26 ตัวถือว่า O(1))
• พื้นที่: O(1) - array ขนาดคงที่ 26

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับใช้ logic required และ while loop ซับซ้อนเกินไปและอาจมีบั๊ก ใช้วิธีเปรียบเทียบ array ตรงๆ (cnt1 == cnt2) เรียบง่ายและถูกต้องกว่า (C++ vector รองรับ operator==)