Số lần xuất hiện tối đa của chuỗi con trong C++

Cho chuỗi s, tìm số lần xuất hiện tối đa của bất kỳ chuỗi con nào thỏa mãn:

• Số ký tự khác nhau trong chuỗi con ≤ maxLetters.
• Độ dài chuỗi con trong khoảng [minSize, maxSize].

Ví dụ: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4. Kết quả: 2. Chuỗi con "aab" xuất hiện 2 lần, có 2 ký tự khác biệt, độ dài 3.

Giải thuật (Cửa sổ trượt)

1. Map m đếm tần suất chuỗi con hợp lệ.
2. Duyệt sz từ minSize đến maxSize:
3. Map x đếm ký tự trong cửa sổ, chuỗi temp.
4. Khởi tạo cửa sổ đầu tiên kích thước sz.
5. Trượt cửa sổ: nếu số ký tự khác biệt ≤ maxLetters, tăng m[temp].
6. Cập nhật cửa sổ: bỏ ký tự đầu, thêm ký tự mới.
7. Tìm giá trị lớn nhất trong m.

Ví dụ C++

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

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> m;
        for(int sz = minSize; sz <= maxSize; sz++) {
            unordered_map<char, int> x;
            string temp = "";
            for(int i = 0; i < sz; i++) {
                x[s[i]]++; temp += s[i];
            }
            for(int j = 0, i = sz; i < s.size(); i++, j++) {
                if(x.size() <= maxLetters) m[temp]++;
                x[temp[0]]--;
                if(x[temp[0]] == 0) x.erase(temp[0]);
                temp.erase(temp.begin(), temp.begin() + 1);
                x[s[i]]++; temp += s[i];
            }
            if(x.size() <= maxLetters) m[temp]++;
        }
        int ans = 0;
        for(auto &p : m) ans = max(ans, p.second);
        return ans;
    }
};

int main() {
    Solution ob;
    cout << (ob.maxFreq("aababcaab", 2, 3, 4));
    return 0;
}

Đầu vào

"aababcaab" 2 3 4

Đầu ra

2