Longest Substring Without Repeating Characters

Bài toán

Cho một chuỗi s. Tìm độ dài của chuỗi con (substring) dài nhất không chứa ký tự nào lặp lại.

Ví dụ:

Input: s = "abcabcbb"
Output: 3
Giải thích: "abc" là dài nhất.

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Thử mọi chuỗi con s[i...j]. Với mỗi chuỗi, check xem có trùng lặp không ($O(n)$). Tổng cộng $O(n^3)$.

Cách 2: Sliding Window (Cửa sổ trượt)

Ta duy trì một cửa sổ [left, right] chứa chuỗi hợp lệ hiện tại. Mở rộng right sang phải từng bước:

1. Kiểm tra ký tự s[right] có nằm trong cửa sổ không?
2. Nếu ĐÃ CÓ (trùng lặp):
   • Đã vi phạm quy tắc. Ta phải thu hẹp cửa sổ từ bên trái (left++) cho đến khi đẩy được ký tự trùng lặp kia ra ngoài.
   • Xóa các ký tự bị loại bỏ khỏi tập theo dõi.
3. Nếu CHƯA CÓ:
   • Thêm s[right] vào tập theo dõi.
   • Cập nhật max length.

Cấu trúc dữ liệu: Dùng Set để kiểm tra trùng lặp trong $O(1)$.

function lengthOfLongestSubstring(s: string): number {
    const charSet = new Set<string>();
    let l = 0;
    let maxLen = 0;

    for (let r = 0; r < s.length; r++) {
        // Nếu ký tự s[r] đã tồn tại, thu hẹp cửa sổ từ bên trái
        while (charSet.has(s[r])) {
            charSet.delete(s[l]);
            l++;
        }

        // Thêm ký tự mới vào cửa sổ
        charSet.add(s[r]);
        
        // Cập nhật kết quả
        maxLen = Math.max(maxLen, r - l + 1);
    }

    return maxLen;
}

Mô phỏng chạy với "dvdf":

1. r=0 ('d'). Set: {d}. Max: 1.
2. r=1 ('v'). Set: {d, v}. Max: 2.
3. r=2 ('d'). Trùng 'd'!
   • while: Xóa s[0] ('d'). l tăng lên 1.
   • Set giờ là {v}. Hết trùng.
   • Add 'd' mới. Set: {v, d}. Max: 2 (vẫn thế).
4. r=3 ('f'). Set: {v, d, f}. Max: 3.

• Time Complexity: $O(n)$ - Mỗi ký tự được thêm vào Set 1 lần và xóa khỏi Set tối đa 1 lần. (2 vòng duyệt nhưng tổng chi phí vẫn tuyến tính).
• Space Complexity: $O(n)$ - Scase xấu nhất Set chứa cả bảng ký tự.

Pattern Nhận Diện

Khi bài toán yêu cầu tìm "Max/Min/Longest/Shortest" trên một mảng/chuỗi con liên tiếp, hãy nghĩ đến Sliding Window. Cấu trúc chung:

for (right) {
    add(right)
    while (condition_false) {
        remove(left)
        left++
    }
    update_result()
}