Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
Longest Substring Without Repeating Characters
Table of Contents
1. Cách tiếp cận vấn đề
Yêu cầu của bài toán đúng như tiêu đề của nó: Cho trước chuỗi s, tìm chiều dài của chuỗi con dài nhất mà không có ký tự nào bị trùng nhau.
Ví dụ:
Input: s = "abcabcbb"
Output: 3
Explanation: Đáp án là "abc", với chiều dài là 3. Lưu ý rằng "bca" và "cab" cũng là những đáp án đúng với cùng chiều dài là 3.
Lưu ý: Chuỗi con "Substring” có nghĩa là một đoạn liên tiếp trong chuỗi, không phải "subsequence"
Nếu xử lý theo kiểu Bruteforce “kiểm tra mọi substring” thì sẽ rất chậm, ta cần tìm 1 giải thuật đáp ứng được các điều kiện sau:
- Có thể mở rộng nhất có thể chiều dài của chuỗi con s cho đến khi gặp phần tử bị trùng c
- Có thể tái thiết lập được chuỗi con s mới từ vị trí của phần tử bị trùng với c trong chuỗi s trước đó
2. Solution & Phân Tích
Để đáp ứng các điều kiện đã nêu với độ phức tạp hợp lý, chúng ta sẽ áp dụng kỹ thuật "Sliding Window" để giải quyết bài toán này. Sử dụng hai con trỏ left và right để duy trì một cửa sổ s[left..right] sao cho cửa sổ luôn hợp lệ (không ký tự lặp). Khi đưa right tiến thêm một vị trí:
- Nếu ký tự mới không lặp, mở rộng cửa sổ.
- Nếu ký tự mới gây lặp, ta dịch left tới khi loại bỏ được ký tự lặp đó.
Mỗi ký tự được xử lý (vào/ra cửa sổ) tối đa một lần → thời gian ~ O(n).
Về cách thức lưu trữ, ta dùng 1 biến ans để lưu giá trị max, và trong Java ta có thể dùng Set để lưu các phần tử không bị trùng lặp, tương ứng:
- Nếu mở rộng được cửa sổ, ta sẽ thêm phần tử đó vào Set
- Nếu phát hiện lặp, ta sẽ dịch left và mỗi lần như vậy sẽ so sánh kết quả max hiện tại với kích thước hiện tại của Set
Còn một cách tối ưu hơn là thay vì dịch left từ từ cho đến khi loại bỏ được ký tự lặp, ta có thể dùng 1 Map để lưu lại lastIndex của từng ký tự và có thể cập nhật lại cửa sổ mới một cách nhanh chóng.
Time-complexity: O(n)
Space-complexity: O(n)
n: Số lượng các ký tự trong chuỗi s.
3. Code
