【解題筆記】Leetcode#3 — Longest Substring Without Repeating Characters

Photo by Chris Ried on Unsplash

還不清楚如何運用Sliding Window方法解題，可以先參考【演算法筆記】Sliding Window 文章

Problem

題號：Leetcode 3
標題：Longest Substring Without Repeating Characters
演算法：Sliding Window

Solution

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var s = Array(s)
        var map = [Character: Int]()
        var maxLen = 0
        var left = 0

        //遍歷s所有的元素(char)，藉此向右移動right指標
        for (right, char) in s.enumerated() {
            
            //縮減window範圍：新加入的元素已經出現過，且元素上一次出現的位置(>= left指標)在window範圍內，left指標移到元素上一次出現位置的右邊(+1)
            if let charIndex = map[char], charIndex >= left {
                left = charIndex + 1
            }
            
            //擴增window範圍
            map[char] = right

            //記錄最大的連續不重覆字元的長度
            maxLen = max(maxLen, right - left + 1)
        }

        return maxLen
    }
}