难度

中等

题目

给定一个字符串，返回最长子字符串的长度
Example 如下：

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

思路一

用一个 hash 记录每个字母出现的 index，然后把字符串扫一遍。不出现重复时就往 hash 表里填。出现重复时，从 hash 取出字母出现的 terminalIndex ，把从当前串开头至 terminalIndex 的字母都从 hash 中清掉。时间复杂度：O(n)。

思路二

不需要存字母出现的 index，出现重复时直接从当前串开头至出现重复字母的位置清掉 hash 即可。这种情况下也不需要用 Dictionary 存 hash，只需用 Set 即可。时间复杂度：O(n)。

代码

方法一

func lengthOfLongestSubstring(_ s: String) -> Int {
    
    // 记录字符的索引值
    var letterAppearedDict = [Character:Int]()
    // 记录长度最大值
    var maxLength = 0
    // 记录当前最大长度
    var currentLength = 0
    
    var chars = [Character](s)
    
    for index in 0 ..< chars.count {
        let char = chars[index]
        
        if letterAppearedDict[char] == nil { // 如果当前字符没有记录索引值，则添加索引并将当前长度加一
            letterAppearedDict[char] = index
            currentLength += 1
        } else { // 如果已经存在索引，则需要将之前索引及索引前的值清空
            // 起点索引值
            let originIndex = index - currentLength
            // 上一个重复点的索引值
            let terminalIndex = letterAppearedDict[char]!
            
            for clearIndex in originIndex ... terminalIndex {
                letterAppearedDict[chars[clearIndex]] = nil
            }
            letterAppearedDict[char] = index
            currentLength = index - terminalIndex
        }
        
        maxLength = max(maxLength, currentLength)
    }
    
    return maxLength
}

方法一

func lengthOfLongestSubstring(_ s: String) -> Int {
    var maxLength = 0
    
    var chars = [Character](s)
    
    guard chars.count > 1 else {
        return chars.count
    }
    
    for index in 0 ..< chars.count - 1 {
        var letterAppearedSet = Set<Character>()
        var length = 1
        while length <= chars.count - index {
            let char = chars[index + length - 1]
            print("char = \(char), index = \(index), length = \(length), letterAppearedSet = \(letterAppearedSet)")
            if letterAppearedSet.contains(char) { // 已经出现重复，后面不可能再有解了
                break
            }
            
            letterAppearedSet.insert(char)
            
            maxLength = max(maxLength, length)
            length += 1
        }
    }
    
    return maxLength
}