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

Cho chuỗi s, tìm độ dài chuỗi con liên tiếp dài nhất chứa tối đa 2 ký tự khác nhau.

Ví dụ

Đầu vào: "eceba"
Đầu ra: 3 (chuỗi con "ece").

Thuật toán cửa sổ trượt (Sliding Window)

Mở rộng khái sang bài toán tổng quát tối đa K ký tự khác biệt:

1. Duy trì cửa sổ [i, j] và unordered_map<char, int> count tần suất ký tự.
2. Mở rộng j: tăng count[s[j]], nếu ký tự mới (count == 1) tăng distinct.
3. Khi distinct > K: thu hẹp cửa sổ từ trái (i++), giảm count[s[i]], nếu về 0 giảm distinct.
4. Cập nhật ans = max(ans, j - i + 1).

Triển khai C++

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

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> cnt;
        int distinct = 0, ans = 0;
        for (int i = 0, j = 0; j < s.size(); ++j) {
            if (++cnt[s[j]] == 1) ++distinct;
            while (distinct > k) {
                if (--cnt[s[i]] == 0) --distinct;
                ++i;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
    int lengthOfLongestSubstringTwoDistinct(string s) {
        return lengthOfLongestSubstringKDistinct(s, 2);
    }
};

Độ phức tạp

• Thời gian: O(N) - mỗi ký tự vào/ra cửa sổ tối đa một lần.
• Không gian: O(K) - bản đồ tần suất tối đa K phần tử.

Kết quả kiểm thử

Đầu vào: "eceba"
Đầu ra: 3