給定一個字串
s，找出不含重複字元的最長子字串長度。
Example:
Input: s = “abcabcbb” Output: 3
Intuition
TIP
用滑動視窗維護一個「無重複字元」的子字串，遇到重複時收縮左邊界。
- 右邊界持續擴展，將字元加入視窗
- 當發現重複字元時，移動左邊界直到視窗內沒有重複
- 用 HashSet 或 HashMap 追蹤視窗內的字元
Approaches
1. Brute Force — O(n³) / O(min(n, m))
- Idea: 檢查所有子字串是否包含重複字元，找出最長的
- Time:
O(n³) - Space:
O(min(n, m))，m 為字元集大小
Brute Force Code
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
var result = 0
for (i in s.indices) {
val seen = mutableSetOf<Char>()
for (j in i until s.length) {
if (s[j] in seen) break
seen.add(s[j])
result = maxOf(result, j - i + 1)
}
}
return result
}
}⭐ 2. Sliding Window + HashMap — O(n) / O(min(n, m))
- Idea: 用 HashMap 記錄每個字元最後出現的位置，遇到重複時直接跳過左邊界
- Time:
O(n) - Space:
O(min(n, m))
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
val map = mutableMapOf<Char, Int>()
var left = 0
var result = 0
for (right in s.indices) {
if (s[right] in map) {
left = maxOf(left, map[s[right]]!! + 1)
}
map[s[right]] = right
result = maxOf(result, right - left + 1)
}
return result
}
}WARNING
收縮左邊界時要用 maxOf(left, ...)，因為重複字元的上次位置可能在目前左邊界之前（已經被移除的區域）。
🔑 Takeaways
- Pattern: 可變長度滑動視窗
- Key trick: HashMap 記錄字元最後出現位置，可以讓左邊界直接跳到正確位置，避免逐步收縮