Permutation in String trong C++

Cho hai chuỗi s1, s2. Kiểm tra s2 có chứa hoán vị của s1 hay không (tức là tồn tại substring của s2 là hoán vị của s1).

Ví dụ: s1="abc", s2="findcab" → true vì "cab" là hoán vị của "abc".

Giải thuật (Sliding Window + Count)

• Mảng cnt1[26], cnt2[26] đếm tần suất.
• Đếm cnt1 cho s1.
• Cửa sổ trượt trên s2:
  • Mở rộng phải: tăng cnt2[s2[i]], nếu ký tự cần thiết thì giảm required.
  • Thu hẹp trái: nếu cnt2[s2[j]] - 1 >= cnt1[s2[j]] thì giảm cnt2, j++.
  • Nếu độ dài cửa sổ = s1.size() và required == 0 → true.
• Trả về false.

Ví dụ code

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

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> cnt1(26), cnt2(26);
        for (char c : s1) cnt1[c-'a']++;
        int j = 0, required = s1.size();
        for (int i = 0; i < s2.size(); i++) {
            char x = s2[i];
            cnt2[x-'a']++;
            if (cnt1[x-'a'] && cnt2[x-'a'] <= cnt1[x-'a']) required--;
            while (j <= i && cnt2[s2[j]-'a'] - 1 >= cnt1[s2[j]-'a']) {
                cnt2[s2[j]-'a']--;
                j++;
            }
            if (i - j + 1 == s1.size() && required == 0) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    cout << ob.checkInclusion("abc", "findcab");
    return 0;
}

Input

"abc" "findcab"

Output

1