3. 无重复字符的最长子串

题目：Leetcode 3.无重复字符的最长子串 (中等) (二刷)

解题思路

这道题目可以采用滑动窗口的思想，有一点点类似TCP的滑动窗口协议的算法思想。

在移动中会根据是否子串内存在重复的字符，来决定是否丢弃一段字符子串。

换句话来说，当列表中出现相同的两个字符时，丢弃第一个字符自身和其前面的所有字。
把第二个字符加进来，更新count。

最后因为最后一个字符可能是重复，也可能是不重复，因此只要去max(temp_count,count)
就可以了。

时间复杂度O(n)

空间复杂度O(k),最坏的情况下O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        count = 0
        temp_count = 0
        result  = []
        for i in s:
            if i not in result:
                result.append(i)
                count+=1
            else:
                if temp_count<count:
                    temp_count = count
                del result[0:result.index(i)+1]
                result.append(i)
                count = len(result)
        return max(count,temp_count)

注：看到有个老哥使用动态规划来解此题，我分析了下它的时间复杂度最坏的情况下
O(n²),其实本题使用动态规划来解并不好。后面会有一题求回文子串的话用动态规划解比较好。