Hiểu bài toán

Cho một chuỗi s gồm các ký tự in hoa từ A đến Z. Nhiệm vụ là tìm độ dài ngắn nhất của một chuỗi con liên tiếp trong s mà chứa tất cả 26 ký tự latin in hoa. Nếu không t tồn tại chuỗi con nào thỏa mãn, in ra -1.

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

Cách Two Pointers (Sliding Window)

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    int freq[26] = {0};
    int count = 0;
    int min_len = INT_MAX;
    int left = 0;

    for (int right = 0; right < n; ++right) {
        // Mở rộng cửa sổ sang phải
        if (freq[s[right] - 'A'] == 0) {
            count++;
        }
        freq[s[right] - 'A']++;

        // Thu hẹp cửa sổ sang trái khi đã đủ 26 ký tự
        while (count == 26) {
            min_len = min(min_len, right - left + 1);

            // Loại bỏ ký tự trái cùng
            freq[s[left] - 'A']--;
            if (freq[s[left] - 'A'] == 0) {
                count--;
            }
            left++;
        }
    }

    if (min_len == INT_MAX) cout << -1;
    else cout << min_len;

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Sử dụng kỹ thuật Sliding Window (Cửa sổ trượt). Duyệt chuỗi từ trái sang phải bằng con trỏ right. Dùng một mảng đếm tần suất freq và biến count để theo dõi số lượng ký tự khác nhau trong cửa sổ hiện tại. Khi count bằng 26, ta cố gắng thu hẹp cửa sổ bằng cách di chuyển con trỏ left sang phải để tìm độ dài nhỏ nhất. Độ phức tạp thời gian là O(n) vì mỗi phần tử được thêm vào và loại bỏ khỏi cửa sổ tối đa 1 lần.

Cách Hai con trỏ (Cải tiến)

#include <iostream>
#include <map>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int j = 0, present = 0, res = n + 1;
    map<char, int> cnt;

    for (int i = 0; i < n; i++) {
        // Mở rộng cửa sổ từ j
        while (j < n && present < 26) {
            if (cnt[s[j]] == 0) present++;
            cnt[s[j]]++;
            j++;
        }

        if (present == 26) {
            res = min(res, j - i);
        }

        // Giảm tần suất của s[i] để chuẩn bị cho bước tiếp theo
        cnt[s[i]]--;
        if (cnt[s[i]] == 0) present--;
    }

    if (res == n + 1) cout << -1;
    else cout << res;

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là biến thể của Sliding Window. Vòng lặp for đại diện cho con trỏ trái (i). Con trỏ phải (j) chỉ di chuyển về phía trước (không bao giờ lùi lại). Với mỗi i, ta cố gắng đẩy j càng xa càng tốt để có đủ 26 ký tự. Khi đã đủ, ta cập nhật kết quả và chuyển sang i tiếp theo. Cách này cũng đảm bảo độ phức tạp O(n) vì j chỉ chạy từ 0 đến n.

Cách Tối ưu hóa vị trí (Vét cạn)

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

int main() {
    string str;
    cin >> str;
    int n = str.size();

    // Đếm t tổng số lượng ký tự khác nhau từ trái
    map<char, int> mp1;
    int r = -1;
    for(int i = 0; i < n; i++) {
       mp1[str[i]]++;
       if(mp1.size() == 26) {
           r = i;
           break;
       }
    }

    // Đếm tổng số lượng ký tự khác nhau từ phải
    map<char, int> mp2;
    int l = -1;
    for(int i = n - 1; i >= 0; i--) {
        mp2[str[i]]++;
        if(mp2.size() == 26) {
            l = i;
            break;
        }
    }

    if (r == -1 || l == -1) {
        cout << -1;
    } else {
        cout << r - l + 1;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Phương pháp này chỉ tìm được một chuỗi con thỏa mãn chứ không chắc chắn là ngắn nhất. Nó tìm vị trí đầu tiên mà từ đó đủ 26 ký tự (r) và vị trí cuối cùng mà từ đó trở về sau đủ 26 ký tự (l). Nó in ra độ dài r - l + 1. Tuy nhiên, cách này có thể sai với các test phức tạp (ví dụ: chuỗi có tiền tố và hậu tố chứa đủ bộ chữ cái nhưng phần giữa thiếu). Ví dụ: 'ABCDE...Z' + 'AAAA...' + 'ABCDE...Z'. Code mẫu của Solution 3 thực ra chỉ tìm được một chuỗi con thỏa mãn (vị trí bắt đầu muộn nhất và vị trí kết thúc sớm nhất để có bộ chữ cái), nhưng không phải là tối ưu nhất nếu xét tính liên tiếp.

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

Bài học kinh nghiệm

• Sử dụng Sliding Window (hai con trỏ) là cách tiếp cận tối ưu nhất cho bài toán tìm chuỗi con thỏa mãn điều kiện tập hợp.
• Cần theo dõi số lượng các ký tự khác nhau trong cửa sổ hiện tại, không chỉ t tổng số ký tự.
• Mảng đếm tần suất thay vì Map (nếu chỉ dùng cho chữ cái A-Z) sẽ nhanh hơn và tiết kiệm bộ nhớ hơn.

Lỗi thường gặp

• Quên kiểm tra trường hợp không tìm thấy chuỗi con đầy đủ (in ra -1).
• Sử dụng thuật toán lồng nhau (vòng lặp trong vòng lặp) không đúng cách dẫn đến độ phức tạp O(n^2) và bị TLE.
• Lỗi logic khi cập nhật biến đếm số lượng ký tự khác nhau (cần kiểm tra xem tần suất có về 0 không trước khi giảm biến đếm).