Chuỗi con dài nhất có tối đa K ký tự khác nhau trong C++

Cho một chuỗi, tìm độ dài chuỗi con dài nhất chứa tối đa k ký tự khác biệt.

Ví dụ: s = "eceba", k = 2 → Kết quả = 3 (chuỗi con "ece").

Phương pháp giải

Sử dụng kỹ thuật cửa sổ trượt (sliding window) với hai con trỏ i, j. Mở rộng cửa sổ bằng j, đếm ký tự bằng hash map. Khi số ký tự khác biệt > k, thu hẹp cửa sổ bằng i. Cập nhật độ dài lớn nhất.

Ví dụ chương trình

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

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int ans = 0;
        unordered_map m;
        int n = s.size();
        int x = 0; // số ký tự khác biệt
        
        for (int j = 0, i = 0; j < n; j++) {
            m[s[j]]++;
            if (m[s[j]] == 1) x++;
            while (x > k && i <= j) {
                m[s[i]]--;
                if (m[s[i]] == 0) x--;
                i++;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.lengthOfLongestSubstringKDistinct("eceba", 2);
    return 0;
}

Đầu vào

"eceba", 2

Đầu ra

3