Pattern · Cửa sổ trượtTrung bình
Chuỗi Con Dài Nhất Không Ký Tự LặpLongest Substring Without Repeating Characters
Hiểu bài
Cho chuỗi s, tìm độ dài chuỗi con dài nhất không chứa ký tự lặp lại.
Ví dụ:
ts
s = "abcabcbb"
output = 3 // "abc" — chuỗi con dài nhất không lặp
s = "bbbbb"
output = 1 // "b"
s = "pwwkew"
output = 3 // "wke"Chuỗi con ở đây là đoạn liên tục (substring) chứ không phải dãy con rời rạc (subsequence).
Ký tự có thể là chữ, số hay ký hiệu Unicode bất kỳ.
Cách cơ bản
O(n²) time, O(min(n, m)) space — m là kích thước bảng ký tựts
function lengthOfLongestSubstring(s: string): number {
let maxLen = 0
for (let i = 0; i < s.length; i++) {
const seen = new Set<string>()
for (let j = i; j < s.length; j++) {
if (seen.has(s[j])) break // gặp ký tự lặp → dừng chuỗi này
seen.add(s[j])
maxLen = Math.max(maxLen, j - i + 1)
}
}
return maxLen
}Vì sao cách này chậm:
Hai vòng lặp lồng nhau kiểm tra mọi cặp (i, j).
- Với chuỗi 10⁴ ký tự → 10⁸ bước.
- Có thể rút gọn vì khi biết chuỗi [i..j] hợp lệ, ta không cần bắt đầu lại từ đầu.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.