[[434992]]

前言

我們社區從本期開始會將顧毅(Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。微博:@故胤道長[1])的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。

該算法題解的 github 倉庫地址是：https://github.com/soapyigu/LeetCode-Swift[2]

不積跬步，無以至千里;不積小流，無以成江海，Swift社區 伴你前行。

1. 描述

給定一個字符串 s ， 找出最長未重復的子字符串的長度。

2. 示例

示例 1

輸入：s = "abcabcbb" 
輸出：3 
解釋：最長未重復子字符串答案是"abc"，長度為 3。 

示例 2

輸入：s = "bbbbb" 
輸出：1 
解釋：最長未重復子字符串答案是"b"，長度為 1。 

示例 3

輸入：s = "pwwkew" 
輸出：1 
解釋：最長未重復子字符串答案是"wke"，長度為 3。注意答案必須是子字符串，“pwke” 是一個子列，而不是一個子字符串。 

示例 4

輸入：s = "" 
輸出：0 

3. 答案

class LongestSubstringWithoutRepeatingCharacters { 
    func lengthOfLongestSubstring(_ s: String) -> Int { 
        var maxLen = 0, startIdx = 0, charToPos = [Character: Int]() 
        let sChars = Array(s) 
         
        for (i, char) in sChars.enumerated() { 
            if let pos = charToPos[char] { 
                startIdx = max(startIdx, pos) 
            } 
             
            // update to next valid position 
            charToPos[char] = i + 1 
            maxLen = max(maxLen, i - startIdx + 1) 
        } 
         
        return maxLen 
    } 
} 

主要思想：使用字典存儲非重復子字符串的下一個可能有效字符的位置,然后迭代字符串更新 maxLen、dictionary 和遇到重復時的 startIdx。

• 時間復雜度：O(n)
• 空間復雜度：O(n)