Chuỗi con cửa sổ nhỏ nhất trong C++

Cho chuỗi S và T. Tìm cửa sổ con nhỏ nhất trong S chứa tất cả ký tự của T. Ví dụ: S = "ABHDAXCVBAGTXATYCB", T = "ABC" → kết quả: "CVBA".

Giải thuật (Kỹ thuật cửa sổ trượt)

• Tạo map m lưu tần suất ký tự trong T.
• Khởi tạo: length = độ dài S, left = 0, right = 0, ansLeft = 0, ansRight = 0, counter = độ dài T, flag = false.
• Duyệt right từ 0 đến cuối S:
  • c = S[right]. Nếu c có trong m:
    • Nếu m[c] > 0 → giảm counter.
    • Giảm m[c].
  • Khi counter == 0 (đã đủ ký tự):
    • Nếu right - left + 1 <= length → cập nhật length, ansLeft, ansRight, flag = true.
    • Nếu left == right → break.
    • c = S[left]. Nếu c có trong m → tăng m[c], nếu m[c] > 0 → tăng counter.
    • Tăng left.
  • Tăng right.
• Nếu flag = false → trả về rỗng, ngược lại trả về S[ansLeft...ansRight].

Ví dụ minh họa (C++)

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

class Solution {
public:
    string minWindow(string s, string x) {
        map<char, int> m;
        for(int i = 0; i < x.size(); i++) m[x[i]]++;
        int length = s.size();
        int left = 0, right = 0, ansLeft = 0, ansRight = 0;
        int counter = x.size();
        bool flag = false;
        string ans = "";
        while(right < s.size()) {
            char c = s[right];
            if(m.find(c) != m.end()) {
                if(m[c] > 0) counter--;
                m[c]--;
            }
            while(counter == 0 && left <= right) {
                if(right - left + 1 <= length) {
                    length = right - left + 1;
                    flag = true;
                    ansLeft = left;
                    ansRight = right;
                }
                if(left == right) break;
                c = s[left];
                if(m.find(c) != m.end()) {
                    m[c]++;
                    if(m[c] > 0) counter++;
                }
                left++;
            }
            right++;
        }
        if(!flag) return ans;
        for(int i = ansLeft; i <= ansRight; i++) ans += s[i];
        return ans;
    }
};

int main() {
    Solution ob;
    cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
    return 0;
}

Đầu vào

"ABHDAXCVBAGTXATYCB" "ABC"

Đầu ra

CVBA