3. Longest Substring Without Repeating Characters
Tags:
Medium
Skills:
String
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm độ dài của chuỗi con liên tiếp dài nhất không có ký tự lặp lại trong một chuỗi cho trước
Phân tích & ý tưởng
Bài tập này có hai hướng tiếp cận chính
Approach - sliding window
left, right = 0, một biến max_len để lưu kết quả, và một hashmap char_index để lưu vị trí xuất hiện cuối cùng của từng ký tựright từ 0 tới hết chuỗiright đã xuất hiện và nằm trong window hiện tại (tức là chỉ số lớn hơn hoặc bằng left ). Cập nhật left tới sau vị trí lặpmax_len = max(max_len, right - left + 1) rightTime and space complexity - sliding window
Solution
1function lengthOfLongestSubstring(s: string): number {
2 let left = 0;
3 let char_index: Map<string, number> = new Map();
4 let max_len = 0;
5 for (let right = 0; right < s.length; right++) {
6 const c = s[right];
7 if (char_index.has(c) && char_index.get(c)! >= left) {
8 left = char_index.get(c) + 1
9 }
10
11 char_index.set(c, right)
12 max_len = Math.max(max_len, right - left + 1)
13 }
14
15 return max_len
16};