Hiểu bài toán

Cho một xâu S chỉ chứa các ký tự chữ cái. Nhiệm vụ là tìm xâu con liên tiếp dài nhất sao cho mọi ký tự trong xâu con đó xuất hiện chính xác một lần (không lặp lại). Nói cách khác, cần tìm đoạn con dài nhất không chứa ký tự lặp.

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

Cách Sliding Window với mảng tần suất (Two Pointers)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

    string s;
    cin >> s;
    int n = s.size();

    vector<int> cnt(256, 0); // Mảng đếm tần suất các ký tự ASCII
    int left = 0;
    int max_len = 0;

    for (int right = 0; right < n; ++right) {
        unsigned char c = s[right];
        cnt[c]++;

        // Nếu ký tự vừa thêm vào bị lặp (cnt > 1), ta cần co cửa sổ lại
        // đến khi loại bỏ hết ký tự lặp đó
        while (cnt[c] > 1) {
            cnt[s[left]]--;
            left++;
        }

        // Cập nhật kết quả
        max_len = max(max_len, right - left + 1);
    }

    cout << max_len;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1) (mảng 256 phần tử)

Sử dụng kỹ thuật Sliding Window (hai con trỏ). Duy trì một cửa sổ [left, right] là xâu con đang xét. Dùng mảng cnt để đếm tần suất các ký tự trong cửa sổ hiện tại.

• Khi duyệt right từ trái sang phải:
  • Tăng đếm cho ký tự tại s[right].
  • Nếu tần suất ký tự này > 1 (tức có lặp), ta phải thu hẹp cửa sổ từ bên trái (left) cho đến khi tần suất của s[right] về lại 1.
  • Cập nhật độ dài lớn nhất: right - left + 1. Độ phức tạp thời gian là O(n) vì mỗi phần tử được duyệt bởi right và left tối đa 1 lần.

Cách Sliding Window tối ưu (Lưu vị trí xuất hiện)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

    string s;
    if (!getline(cin, s)) return 0; // Đọc cả dòng nếu có khoảng trắng

    // Xử lý nếu input có nhiều dòng hoặc chỉ một dòng, 
    // nhưng theo đề bài là một xâu duy nhất.
    // Dưới đây là cách dùng mảng lưu vị trí cuối để nhảy nhanh.

    vector<int> lastSeen(256, -1);
    int best = 0;
    int left = 0;

    for (int right = 0; right < s.size(); ++right) {
        unsigned char c = (unsigned char)s[right];

        // Nếu ký tự này đã xuất hiện trong cửa sổ hiện tại (vị trí >= left)
        if (lastSeen[c] >= left) {
            // Ta có thể nhảy left ngay đến vị trí sau của lần xuất hiện trước đó
            left = lastSeen[c] + 1;
        }

        // Cập nhật vị trí xuất hiện cuối của ký tự
        lastSeen[c] = right;

        // Cập nhật độ dài lớn nhất
        best = max(best, right - left + 1);
    }

    cout << best;
    return 0;
}

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

Cải tiến từ phương pháp Sliding Window cơ bản. Thay vì dùng vòng lặp while để giảm left từng bước, ta dùng mảng lastSeen để lưu vị trí xuất hiện gần nhất của mỗi ký tự.

• Khi duyệt qua s[right]:
  • Kiểm tra xem s[right] có nằm trong cửa sổ hiện tại không bằng cách so sánh lastSeen[c] với left.
  • Nếu có (tức là lặp), ta không cần giảm left từng bước mà có thể nhảy thẳng left = lastSeen[c] + 1 để loại bỏ phần lặp.
  • Cập nhật lastSeen[c] = right. Cách này giúp loại bỏ hoàn toàn vòng lặp while, tối ưu hơn về mặt thời gian thực tế (giảm số bước lặp lặp lại), mặc dù độ phức tạp Big-O vẫn là O(n).

Cách Brute Force (Tối đa hóa theo cách cũ)

// Lưu ý: Code này chỉ mang tính tham khảo, độ phức tạp O(n^2)
// Có thể gây TLE với n = 50,000
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    int max_len = 0;

    // Duyệt mọi vị trí bắt đầu
    for (int i = 0; i < n; i++) {
        vector<bool> visited(256, false);
        for (int j = i; j < n; j++) {
            if (visited[s[j]]) {
                break; // Phát hiện lặp, dừng đoạn con tại đây
            }
            visited[s[j]] = true;
            max_len = max(max_len, j - i + 1);
        }
    }
    cout << max_len;
    return 0;
}

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

Duyệt tất cả các cặp (i, j) để tạo ra mọi xâu con liên tiếp. Với mỗi xâu con, dùng một mảng đánh dấu để kiểm tra xem có ký tự nào lặp lại không. Nếu lặp thì dừng lại. Phương pháp này quá chậm để pasado với độ dài xâu lên tới 50,000 (vì khoảng 50,000^2 = 2.5 * 10^9 thao tác).

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

Bài học kinh nghiệm

• Bài toán này là bài toán kinh điển về 'Dãy con liên tiếp không chứa phần tử lặp lại' (Longest Substring Without Repeating Characters).
• Kỹ thuật Sliding Window (hai con trỏ) là chìa khóa để giải quyết bài toán này với độ phức tạp O(n). Cửa sổ luôn duy trì tính chất 'không lặp'.
• Khi gặp ký tự lặp, ta cần loại bỏ các ký tự ở bên trái cho đến khi ký tự lặp bị loại bỏ.

Lỗi thường gặp

• Quên cập nhật lại tần suất của ký tự bị loại bỏ khi thu hẹp cửa sổ (bên trái).
• Lầm tưởng rằng độ dài xâu con không lặp bao giờ cũng tăng lên khi duyệt thêm ký tự. Thực tế, nếu gặp lặp, độ dài có thể giảm hoặc giữ nguyên sau khi điều chỉnh left.
• Xử lý sai phạm vi ký tự (ví dụ bỏ qua các ký tự đặc biệt hoặc hoa/thường nếu không dùng unsigned char hoặc mảng đủ 256).