Longest Substring Without Repeating Characters: cửa sổ biết lúc nào cần thu hẹp

Bài toán nghe có vẻ đơn giản: tìm đoạn ký tự liên tiếp dài nhất mà không có gì lặp lại. Mở rộng cửa sổ cho đến khi gặp ký tự trùng, ghi lại độ dài, rồi tiếp tục. Điểm mấu chốt là khi ký tự trùng xuất hiện, bạn không thể bắt đầu lại từ đầu — bạn đã thấy mọi thứ bên trái chỗ va chạm đó, và phần lớn kiến thức đó vẫn còn giá trị.

Khoảng cách giữa "bắt đầu lại" và "nhảy thẳng đến vị trí đúng" chính là toàn bộ sự khác biệt giữa O(n^2) và O(n).

Đề bài

Cho một chuỗi s, tìm độ dài của substring dài nhất mà không chứa ký tự lặp lại — mỗi ký tự trong cửa sổ phải xuất hiện đúng một lần. Đề gốc: LeetCode 3.

Ràng buộc:
- 0 <= s.length <= 5 * 10^4
- s gồm các chữ cái tiếng Anh, chữ số, ký hiệu và khoảng trắng.

Constraints nói gì trước khi bạn viết một dòng code

Độ dài chuỗi là 0 <= s.length <= 5 * 10^4. 50,000 ký tự. Giới hạn này loại bỏ ngay mọi thuật toán bậc ba: brute force sinh ra O(n^2) substring và kiểm tra từng cái trong O(n) cho tổng O(n^3) — khoảng 1.25 * 10^14 phép tính với input xấu nhất. Không thể chạy xong trong thời gian thực tế.

Ngay cả O(n^2) cũng căng. Mục tiêu là O(n).

Bộ ký tự gồm chữ cái, số, ký hiệu và khoảng trắng — tức là bất kỳ ký tự ASCII nào. Tối đa 128 giá trị phân biệt. Điều này quan trọng: số ký tự duy nhất trong bất kỳ cửa sổ nào bị giới hạn bởi một hằng số nhỏ (128), không phải độ dài chuỗi. Dùng hash map hay mảng kích thước cố định 128 phần tử không tạo ra sự khác biệt về mặt thuật toán; hash map chỉ dễ đọc hơn.

Chuỗi rỗng nằm trong giới hạn hợp lệ. Kết quả trả về 0, và cả hai cách giải đều xử lý trường hợp này mà không cần kiểm tra riêng.

Approach 1: Brute force — sinh ra tất cả và kiểm tra từng cái

Đọc thẳng từ đề bài: thử mọi vị trí bắt đầu có thể, mở rộng cho đến khi gặp ký tự lặp, và theo dõi độ dài tối đa.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
 
        for i in range(n):
            seen = set()
            for j in range(i, n):
                if s[j] in seen:
                    break
                seen.add(s[j])
                max_length = max(max_length, j - i + 1)
 
        return max_length

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int n = s.Length;
        int maxLength = 0;
 
        for (int i = 0; i < n; i++) {
            var seen = new HashSet<char>();
            for (int j = i; j < n; j++) {
                if (seen.Contains(s[j])) break;
                seen.Add(s[j]);
                maxLength = Math.Max(maxLength, j - i + 1);
            }
        }
 
        return maxLength;
    }
}

Vòng lặp trong dừng ngay khi gặp ký tự trùng, nên thực tế chặt hơn O(n^3) — bạn không kiểm tra toàn bộ substring mỗi lần mà duyệt từng ký tự với early exit. Nhưng worst case vẫn là O(n^2): chuỗi như "abcde...z" với mọi ký tự đều khác nhau khiến vòng lặp trong chạy đến n cho mọi chỉ số ngoài.

Time: O(n^2). Space: O(min(m, n)) với m là kích thước bảng chữ cái (128 cho ASCII). Set không bao giờ chứa nhiều hơn min(m, n) phần tử.

Vấn đề cốt lõi: khi bắt đầu từ index i + 1, bạn vứt bỏ mọi thứ đã học được từ lần chạy bắt đầu tại i. Bạn sẽ xây lại cùng một seen set từng ký tự một, dù phần giao nhau giữa các cửa sổ liên tiếp rất lớn. Sự dư thừa đó chính là thứ sliding window loại bỏ.

Approach 2: Sliding window với hash map — nhảy qua, không bắt đầu lại

Thay vì reset toàn bộ cửa sổ khi gặp ký tự trùng, bạn giữ right pointer tiến liên tục về phía trước và chỉ đẩy left pointer đủ xa để loại bỏ xung đột.

Ý tưởng cốt lõi: khi s[right] trùng với ký tự đã có trong cửa sổ, ranh giới left hợp lệ sớm nhất là prev_index + 1, trong đó prev_index là lần cuối s[right] xuất hiện. Hash map từ ký tự đến chỉ số lần xuất hiện cuối cùng cho bạn vị trí đó trong O(1).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_map = {}
        left = 0
        max_length = 0
 
        for right in range(len(s)):
            ch = s[right]
            if ch in char_map and char_map[ch] >= left:
                left = char_map[ch] + 1
            char_map[ch] = right
            max_length = max(max_length, right - left + 1)
 
        return max_length

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        var charMap = new Dictionary<char, int>();
        int left = 0;
        int maxLength = 0;
 
        for (int right = 0; right < s.Length; right++) {
            char ch = s[right];
            if (charMap.ContainsKey(ch) && charMap[ch] >= left) {
                left = charMap[ch] + 1;
            }
            charMap[ch] = right;
            maxLength = Math.Max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

Điều kiện char_map[ch] >= left tinh tế và dễ bị bỏ qua. Các ký tự xuất hiện trước ranh giới left hiện tại không còn nằm trong cửa sổ nữa — chúng là các entry cũ trong map. Nếu bạn thấy s[right] = 'a' và map cho biết 'a' xuất hiện lần cuối ở index 1, nhưng left đã là 3, thì 'a' thực ra không có trong cửa sổ hiện tại. Di chuyển left ngược lại sẽ sai. Bạn chỉ di chuyển left khi va chạm là thật — khi index được lưu vẫn nằm trong [left, right).

Time: O(n). Right pointer tiến đúng n bước. Left pointer cũng chỉ tiến về phía trước và không bao giờ vượt qua right, nên tổng cộng đóng góp tối đa n bước trong toàn bộ vòng lặp. Mỗi thao tác hash map là O(1). Space: O(min(m, n)) — giới hạn giống brute force, cùng lý do.

Trace tay "abcabcbb" từng bước

Ở bước 3 (right=3, 'a'): map cho thấy 'a' xuất hiện lần cuối ở index 0, nằm trong [left=0, right=3). Di chuyển left về 1. Cửa sổ giờ là "bca" — vẫn độ dài 3.

Ở bước 4 (right=4, 'b'): 'b' xuất hiện lần cuối ở index 1, nằm trong [left=1, right=4). Di chuyển left về 2. Cửa sổ thành "cab", vẫn độ dài 3.

Lưu ý chúng ta không bao giờ quay lại kiểm tra "a" hay "b" từng cái một — hash map cho chúng ta biết chính xác cần nhảy đến đâu. Đến cuối, max_length là 3, khớp với kết quả mong đợi.

Các edge case

Chuỗi rỗng (s = ""): vòng lặp không chạy lần nào. Trả về 0. Không cần xử lý riêng.

Một ký tự (s = "a"): right=0, 'a' chưa có trong map, char_map = {a:0}, max_length = 1. Trả về 1.

Toàn ký tự giống nhau (s = "aaaa"): ở right=1, 'a' có trong map ở index 0, 0 >= left=0, nên left = 1. Ở right=2, 'a' có trong map ở index 1, 1 >= left=1, nên left = 2. Cửa sổ luôn chứa đúng một ký tự. Trả về 1.

Toàn ký tự khác nhau (s = "abcde"): left không bao giờ di chuyển. Cửa sổ mở rộng đến toàn bộ chiều dài. Trả về len(s).

Ký tự xuất hiện trước cửa sổ hiện tại (s = "abba"): ở right=3, 'a' có trong map ở index 0. Nhưng sau khi xử lý 'b' hai lần, left đã là 2. Index 0 < left=2, nên char_map['a'] >= left là false — chúng ta không di chuyển left ngược lại. Cửa sổ giữ nguyên ở "a", độ dài 1. Trả về 2 (từ cửa sổ "ab" ở right=1).

Khoảng trắng và ký hiệu (s = "ab c@1"): hash map xử lý bất kỳ ký tự nào một cách minh bạch. Khoảng trắng ở index 2 và '@' ở index 4 chỉ là các key thông thường. Không cần xử lý đặc biệt.

Bảng so sánh

Space giống nhau cho cả hai. Sự khác biệt duy nhất là có lặp lại công việc hay không.

Pattern bên dưới và điều cần rút ra

Bài này là ví dụ kinh điển của sliding window kiểu "expand rồi shrink". Template như sau:

• Right pointer mở rộng cửa sổ vô điều kiện.
• Khi cửa sổ vi phạm điều kiện (ở đây: xuất hiện ký tự trùng), di chuyển left về phía trước cho đến khi điều kiện được phục hồi.
• Theo dõi kết quả ở mỗi bước.

Điều làm bài này khác một chút so với các window problem mà left shrink từng bước (như Minimum Window Substring) là left pointer có thể nhảy nhiều vị trí trong một lần di chuyển. Hash map là thứ cho phép bước nhảy đó — không có nó, bạn phải duyệt left từng ký tự một để tìm và loại bỏ ký tự trùng, quay trở lại gần O(n^2).

Tên pattern cụ thể: last-index hash map bên trong expand-shrink window. Bạn sẽ thấy cấu trúc y hệt này trong:

Longest Repeating Character Replacement (424) — cửa sổ được phép có tối đa k ký tự không phải ký tự chiếm ưu thế. Bạn vẫn theo dõi số lần xuất hiện trong map và shrink left khi cửa sổ vi phạm điều kiện. Cơ chế "ký tự chiếm ưu thế" là mới, nhưng skeleton expand-shrink hoàn toàn giống nhau.

Permutation in String (567) — kiểm tra xem có permutation nào của p xuất hiện như substring trong s không. Bạn duy trì frequency map của các ký tự cần thiết và shrink cửa sổ về kích thước cố định. Cơ chế điều kiện khác, nhưng cùng two-pointer structure điều khiển nó.

Minimum Window Substring (76) — tìm cửa sổ ngắn nhất trong s chứa tất cả ký tự của t. Shrinking là bắt buộc (bạn muốn tối thiểu), nên bạn shrink mạnh mẽ bất cứ khi nào cửa sổ hợp lệ. Logic lật từ longest sang shortest, nhưng vòng lặp cốt lõi vẫn là cùng một nhịp expand-and-shrink.

Longest Substring with At Most K Distinct Characters (340) — tổng quát hóa trực tiếp. Thay vì "zero duplicates allowed", điều kiện là "tối đa k ký tự phân biệt". Thay thế kiểm tra ký tự trùng bằng frequency map và kiểm tra kích thước.

Tôi sẽ dùng sliding window với hash map mà không do dự. Brute force chỉ hữu ích đúng một lần: như reference implementation để kiểm tra giải pháp tối ưu của bạn trên input nhỏ trước khi bạn tin tưởng nó. Trong sản xuất hay phỏng vấn, O(n) với một lần duyệt là câu trả lời.

Vị trí trong series sliding window

Series đến nay đã bao gồm các bài có kích thước cửa sổ cố định (Permutation in String) và các bài mở rộng về phía một mục tiêu (Minimum Window Substring). Bài này là trường hợp đơn giản nhất của variable-size window với exclusion constraint: cửa sổ không được chứa bất kỳ ký tự nào nhiều hơn một lần. Điều kiện đó dễ phát hiện (một lần hash map lookup) và dễ giải quyết (một lần nhảy left pointer). Đây là bài phù hợp để đọc trước khi đối mặt với constraint handling phức tạp hơn trong 424 và 76.