Intuition#

用滑動視窗維護一個「無重複字元」的子字串，遇到重複時收縮左邊界。

• 右邊界持續擴展，將字元加入視窗
• 當發現重複字元時，移動左邊界直到視窗內沒有重複
• 用 HashSet 或 HashMap 追蹤視窗內的字元

Approaches#

1: Brute Force#

• 概念: 檢查所有子字串是否包含重複字元，找出最長的
• 時間複雜度: O(n³)
• 空間複雜度: O(min(n, m))，m 為字元集大小

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#

• 概念: 用 HashMap 記錄每個字元最後出現的位置，遇到重複時直接跳過左邊界
• 時間複雜度: O(n)
• 空間複雜度: 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
    }
}

收縮左邊界時要用 maxOf(left, ...)，因為重複字元的上次位置可能在目前左邊界之前（已經被移除的區域）。

🔑 Takeaways#

• Pattern: 可變長度滑動視窗
• 關鍵技巧: HashMap 記錄字元最後出現位置，可以讓左邊界直接跳到正確位置，避免逐步收縮