LeetCode：最长不含重复字符的子字符串

这是无量测试之道的第212篇原创

题目来源于 LeetCode 的第 3 题，难度为：中等。目前的通过率是37.3%。

解题思路的思考：

  以abcabcbb为例，找出以每个字符结束，不包含重复字符的最长子串。那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

• 以 [a]bcabcbb 结束的最长字符串为[a]bcabcbb,长度为1
• 以 a[b]cabcbb 结束的最长字符串为[ab]cabcbb,长度为2
• 以 ab[c]abcbb 结束的最长字符串为[abc]abcbb,长度为3
• 以 abc[a]bcbb 结束的最长字符串为a[bca]bcbb,长度为3
• 以 abca[b]cbb 结束的最长字符串为ab[cab]cbb,长度为3
• 以 abcab[c]bb 结束的最长字符串为abc[abc]bb,长度为3
• 以 abcabc[b]b 结束的最长字符串为abcab[cb]b,长度为2
• 以 abcabcb[b] 结束的最长字符串为abcabcb[b],长度为1

有点动态规划的意思了，但是不是动态规划。   我们每次找以x结尾的最长子串的时候，都是在上次的最长子串的基础上进行查找。比如在找以abcabcbb中的第4个a结尾的最长子串的时候，我们从上次的最长子串abc的基础上找。

以此类推，每次找以x结尾的最长子串的时候，都是以x前面的那位最长子串的基础上找。比如，本例中的a前的那位是c，c的最长子串是abc。再次基础上开始我们确定以a结尾的最长子串： 我们假定求以x结尾的最长子串，然后x前的那位结尾的最长子串是 #$%^

1. 找x上次出现的位置
2. 分2种情况，
   1. x不在上次的最长子串中，则以x结尾的最长子串就是#$%^x
   2. x在上次的最长子串中，则以x结尾的最长子串就是 %^x

一直遍历到结束，返回最长的那个即可。

代码

 class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.count == 0  { return 0 }
        var li = 0
        var si = 0
        var map = [Character:Int]()
        map[s.first!] = 0
        var maxLength = 1
        for (index,char) in s.enumerated() {
            if index == 0 { continue }
            li = map[char] ?? -1
            if li >= si {
                si = li + 1
            }
            maxLength = max(maxLength, index - si + 1)
            map[char] = index
        }
        return maxLength
    }
}

代码解读

li： lastIndex的缩写 ,表示：比如abcabcaa 现在到第4个位置也就是a ，li表示上次a出现的位置 li = 1

si: startindex的缩写，表示以i-1位置字符结尾的最长不重复字符串的开始索引(最左索引) 比如abcabcaa 第三个位置的c，si =0

map 存的就li的value，key 就是character

结尾

  这个题其实有点动态规划的意思，要是有动态规划的基础，就可以很好的去解这道题。希望能帮助到大家。

end