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

🥈Medium

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题解

滑动窗口

1. 新建一个数组
2. 遍历字符串，如果当前字母不在数组中就加进去
3. 如果已经有一个相同的字母（位置在x）了，记录当前数组的长度，并与max进行比较，得到最长长度
4. 然后把数组x前面的内容删除，加入当前的字母
5. 输出max
6. 注意边界和特殊情况

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)==0:
            return 0
        if len(s)==1 or s==len(s)*s[0]:
            return 1
        a=[]
        max=0
        count=0
        for i in range(len(s)):
            if s[i] not in a:
                a.append(s[i])
            else:
                count=a.index(s[i])
                if len(a)>max:
                    max=len(a)
                a=a[count+1:i]
                a.append(s[i])
        if len(a)>max:
            max=len(a)
        return max

复杂度分析

• 时间复杂度
• 空间复杂度

使用Hash（字典） - 滑动窗口优化

使用字典记录任意字符最近的索引值，字典查询时间复杂度为O(1)，相比数组查询，效率更高
该算法的难点在于理解什么是可抛弃字符串的索引尾值，以及为什么需要dic[c] > start的判断

class Solution(object):
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 可抛弃字符串的索引尾值 - 字符串索引值，该索引值以及之前的字符都属于重复字符串中的一部分，不再在计算中涉及
        ignore_str_index_end = -1
        dic = {}        # 任意字符最后出现在索引的位置 - {字符: 字符索引值}
        max_length = 0  # 最长字符串长度

        for i, c in enumerate(s):
            # 如果字典中已经存在字符c，则字符c重复
            # 如果字符索引值大于ignore_str_index_end，则字符c在需处理的范围内（补充说明请参考备注一）
            if c in dic and dic[c] > ignore_str_index_end:
                # 先更新可抛弃字符串的索引尾值为字符c上一次的索引值
                ignore_str_index_end = dic[c]
                # 再更新字符c的索引值
                dic[c] = i
            # 否则，
            else:
                # 更新字符最近的索引位置
                dic[c] = i
                # 更新最大长度
                max_length = max(i - ignore_str_index_end, max_length)

        return max_length

复杂度分析：

• 时间复杂度：
• 空间复杂度：

备注：
假设有字符串"abbcda", 观察可知最长不重复子串为"bcda"根据编写的算法，在刚遍历至最后一个’a’时，dic['a']的值为0，此时ignore_str_index_end的值已经更新为索引1，索引1以及之前的字符都是出现在重复字符之前，不用再在运算中考虑的字符。
ignore_str_index_end的注释，是可抛弃字符串的索引尾值，是双指针方法中左指针（起始针）的反面;
如果仍然不好理解，可以做到理解双指针法也行，毕竟ignore_str_index_end的确有点绕…

动态规划

一个简单的例子：

已知字符串S1='abcc'，其最长无重复子串是'abc'，问字符串S2='abccd'的最长无重复子串长度是什么？

S1结尾加上’d’之后，最长无重复子串有两种可能的来源：

1. 最长无重复子串包含新增的’d’，即'cd'
2. 最长无重复子串不包含新增的’d’，即S1的最长无重复子串'abc'
   比较'cd'与'abc'，len('abc')>len('cd')，所以S2的最长无重复子串依然是'abc'

推导状态转移方程

根据例子的思路推广至一般的情况：
给出一个字符串Si，已知它的最长子串长度为Li，如果在Si的末尾追加一个字符C，即Si+1=Si+C，那么Si+1的最长子串是多少？

很容易想到：

lengthOfLongestSubString(Si+1)=max(Li,len(C结尾的无重复子串))

思路的具体实现

根据状态转移方程，轻松得到代码，因为查找新增字符结尾的无重复子串长度是向左搜索，所以暂且把这个过程取名叫find_left

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        for i in range(0, len(s)):
            length = max(length, find_left(s, i))
        return length

接下来，求以s为结尾的无重复子串长度，这就非常容易了

def find_left(s, i):
    tmp_str = s[i]
    j = i - 1
    while j >= 0 and s[j] not in tmp_str:
        tmp_str += s[j]
        j -= 1
    return len(tmp_str)

最后考虑一些特殊情况

if s == '':
    return 0
if len(s) == 1:
    return 1

完整的代码:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0
        if len(s) == 1:
            return 1

        def find_left(s, i):
            tmp_str = s[i]
            j = i - 1
            while j >= 0 and s[j] not in tmp_str:
                tmp_str += s[j]
                j -= 1
            return len(tmp_str)
        length = 0
        for i in range(0, len(s)):
            length = max(length, find_left(s, i))
        return length