Hiểu bài toán

Cho một xâu ký tự S độ dài N và một số nguyên K. Tìm xâu con liên tiếp dài nhất của S sao cho không có ký tự nào xuất hiện nhiều hơn K lần. In ra độ dài xâu con đó và vị trí bắt đầu (tính từ 1).

Các cách tiếp cận

Cách Two Pointers (Sliding Window) tối ưu

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("xaucon.inp", "r", stdin);
    freopen("xaucon.out", "w", stdout);

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    vector<int> cnt(26, 0);
    int l = 0;
    int bestLen = 0, bestPos = 1;

    for (int r = 0; r < N; r++) {
        cnt[S[r] - 'a']++;

        while (cnt[S[r] - 'a'] > K) {
            cnt[S[l] - 'a']--;
            l++;
        }

        int len = r - l + 1;
        if (len > bestLen) {
            bestLen = len;
            bestPos = l + 1;
        }
    }

    cout << bestLen << " " << bestPos;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (kích thước bảng 26)

Sử dụng kỹ thuật Sliding Window (hai con trỏ). Con trỏ phải 'r' duyệt qua các ký tự, con trỏ trái 'l' giữ cho window hợp lệ. Khi số lần xuất hiện của ký tự tại 'r' vượt quá K, ta di chuyển 'l' sang phải cho đến khi điều kiện thỏa mãn. Window [l, r] luôn là window kết thúc tại r dài nhất hợp lệ. Ta cập nhật kết quả tại mỗi bước.

Cách Brute Force (Tử giản)

// Pseudocode for illustration
int bestLen = 0, bestPos = 1;
for (int i = 0; i < N; i++) {
    vector<int> cnt(26, 0);
    int maxF = 0;
    for (int j = i; j < N; j++) {
        cnt[S[j] - 'a']++;
        maxF = max(maxF, cnt[S[j] - 'a']);
        if (maxF <= K) {
            int len = j - i + 1;
            if (len > bestLen) {
                bestLen = len;
                bestPos = i + 1;
            }
        } else {
            break; // Rời vòng lặp trong nếu xâu con không hợp lệ
        }
    }
}

• Time Complexity: O(N^2)
• Space Complexity: O(1)

Duyệt tất cả các xâu con liên tiếp. Với mỗi xâu con bắt đầu tại i, ta duyệt kết thúc tại j và cập nhật tần suất. Nếu tần suất lớn nhất vượt quá K, ta dừng duyệt j. Cách này chậm vì duyệt O(N^2) nhưng logic đơn giản.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sliding Window là cách hiệu quả nhất cho bài toán xâu con liên tiếp có ràng buộc về tần suất.
• Việc duy trì một mảng tần suất cố định kích thước 26 giúp cập nhật O(1) khi con trỏ di chuyển.

Lỗi thường gặp

• Quên cập nhật tần suất của ký tự bị loại bỏ (khi dịch chuyển con trỏ trái) hoặc cập nhật sai thứ tự.
• Xử lý sai độ dài xâu con hoặc vị trí bắt đầu (off-by-one error), ví dụ in ra chỉ số 0 thay vì 1.