3. Longest Substring Without Repeating Characters

Problem

Bài toán yêu cầu tìm độ dài của chuỗi con dài nhất trong một chuỗi đầu vào mà không có ký tự nào lặp lại. Đây là một bài toán kinh điển về chuỗi và thường được giải hiệu quả bằng kỹ thuật "sliding window" (cửa sổ trượt) kết hợp với một cấu trúc dữ liệu để kiểm tra sự xuất hiện của ký tự (thường là HashMap hoặc Set).

Approach

Dùng hai pointer left và right để xác định một sliding window trên chuỗi

Duyệt từng ký tự từ trái sang phải (right tăng dần)

Nếu gặp ký tự đã xuất hiện trong window hiện tại, di chuyển pointer left lên sau vị trí xuất hiện trước đó của ký tự này để đảm bảo tất cả ký tự trong window là duy nhất

Tại mỗi bước, cập nhật độ dài lớn nhất của window

💡

Cách này đảm bảo mỗi ký tự chỉ bị duyệt tối đa 2 lần nên TC: O(n), rất tối ưu cho bài này

Solution

typescripttypescript

1function lengthOfLongestSubstring(s: string): number {
2    let map: Map<string, number> = new Map();
3    let left = 0;
4    let max_len = 0;
5    for (let right = 0; right < s.length; right++) {
6        const char = s[right];
7        if (map.has(char) && map.get(char) >= left) {
8            left = map.get(char) + 1;
9        }
10        map.set(char, right)
11        max_len = Math.max(max_len, right - left + 1)
12    }
13
14    return max_len
15};

💡

Giải thích

char_index_map lưu vị trí xuất hiện gần nhất của từng ký tự

Nếu gặp ký tự đã xuất hiện trong window hiện tại (char_index_map.get(current_char)! >= left cập nhật left lên vị trí cũ

Luôn cập nhật max_lenvới độ dài window hiện tại (right - left + 1)

💡

Tại sao có điều kiện map.has(char) && map.get(char) >= left

Giải thích chi tiêt

map.has(char) kiểm tra xem ký tự char đã từng xuất hiện trong chuỗi chưa (tức là đã có lưu trong map chưa)

map.get(char) >= left : Kiểm tra vị trí xuất hiện gần nhất của ký tự char có nằm trong window hiện tại (window từ left -> right ) hay không

Tại sao phải kiểm tra hai điều kiện này?

Nếu chỉ kiểm tra map.has(char) , bạn sẽ di chuyển pointer left lên mỗi khi gặp lại ký tự. Kể cả khi ký tự đó đã năm ngoài window hiện tại, điều này sẽ làm sai thuật toán

Còn nếu chỉ kiểm tra vị trí mà không kiểm tra sự tồn tại, có thể gặp lỗi khi map chưa chứa key đó

Ý nghĩa thực tế

Điều kiện này đảm bảo chỉ khi ký tự lặp lại trong đoạn chuỗi con hiện tại (tức là chưa bị loại khỏi window), ta mới cần dịch pointer trái lên sau vị trí lặp để loại bỏ ký tự trùng

Nếu ký tự lặp lại nằm ngoài window hiện tại (tức là đã bị loại khỏi window), ta không quan tâm và không cần cập nhật left

Loading content...

1function lengthOfLongestSubstring(s: string): number { 2 let map: Map<string, number> = new Map(); 3 let left = 0; 4 let max_len = 0; 5 for (let right = 0; right < s.length; right++) { 6 const char = s[right]; 7 if (map.has(char) && map.get(char) >= left) { 8 left = map.get(char) + 1; 9 } 10 map.set(char, right) 11 max_len = Math.max(max_len, right - left + 1) 12 } 13 14 return max_len 15};

3. Longest Substring Without Repeating Characters

Related Posts

Related Posts

3. Longest Substring Without Repeating Characters

Related Posts

2. Add Two Numbers

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

22. Generate Parentheses

23. Merge k Sorted Lists

Related Posts

2. Add Two Numbers

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

22. Generate Parentheses

23. Merge k Sorted Lists