题目

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

示例

示例 1:

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

示例 2:

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

示例 3:

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

解答

方案1

我们首先考虑用暴力求解法，探究字符串的每一个子串是否不含重复字符，并记录不含重复字符的最长子串。
这里，我们设置i，j为子串两端字符在原字符中的下标索引，用lambda表达式定义一个简易函数no_repetitive_chars，用于判断输入的字符串是否没有重复字符，如果没有返回True。用cur_len记录当前非重复字符串的长度，用max_len记录当前为止最大非重复子串长度。所有子串的可能有(N+1)*N/2个，需要一一判断。

class Solution:
    def lengthOfLongestSubstring(self, s):
        no_repetitive_chars = lambda s: len(list(cur_chars)) == len(set(list(cur_chars)))
        max_len = 0
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                cur_chars = s[i:j]                      # 取当前子串
                if no_repetitive_chars(cur_chars):
                    cur_len = len(cur_chars)            # 当前子串长度
                    max_len = max(cur_len, max_len)     # 当前最长子串长度
        return max_len

不出意料，代码超时，我们需要更换思路。

方案2

如何做到只遍历一次？为了获得更好的时间性能，我们采用算法优化中常用的以空间换时间策略，设输入字符串为s，从头到尾遍历字符串：
1.创建临时字符串变量cur_str，这个字符串中，没有重复字符，并且最后一个字符是当前遍历到的字符；
2.定义下标字典（哈希表）index_dict，字典的键是cur_str中的每一个字符，值为字符对应的s中的下标；
3.从头到尾遍历字符串，查看当前字符串cur_char是否在cur_str中，如果出现过，从字典中取出该字符的位置prev_index，为了保证cur_str中元素不重复，需要把cur_str中第一个字符的开始位置start_index（相对于s）移动到prev_index+1，相当于从prev_index+0.5位置截断cur_str并取后半部分；
4.同时更新下标字典index_dict，删除在start_index之前的所有字符记录，确保index_dict中的所有元素只包含cur_str中的所有字符。
需要留意的是，start_index，prev_index，cur_index等下标变量都是相对于输入字符s的位置。

class Solution(object):
    def lengthOfLongestSubstring(self, s):

        def remove_previous_chars(index_dict, index):
            previous_chars = []
            for char in index_dict.keys():
                if index_dict[char] < index:
                    previous_chars.append(char)
            for char in previous_chars:
                index_dict.pop(char)
        # 相当于{key: value for key, value in index_dict.items() if value >= index}
        # 但是执行会出错不知为何

        if s is None or len(s) == 0:                            # 特殊情况，特殊对待
            return 0

        max_len = start_index = 0
        index_dict = {}                                         # 下标字典，key为字符，value为下标

        for cur_index in range(len(s)):
            cur_char = s[cur_index]                             # 当前字符
            if cur_char in index_dict:
                start_index = index_dict[cur_char] + 1          # 更新当前字符串的起始位置
                remove_previous_chars(index_dict, start_index)  # 更新下标字典
            # cur_str = s[cur_index: start_index+1]             # 当前字符串
            # cur_len = len(cur_str)                            # 当前字符串长度
            cur_len = cur_index - start_index + 1               # 当前字符的长度
            index_dict[cur_char] = cur_index                    # 加入当前字符及其下标
            max_len = max(max_len, cur_len)                     # 当前最大长度
        return max_len

代码通过时间限制，耗时280ms。

方案3

如何能够不用反复删除字典中的元素？这里我们的字典index_dict性质改变，不只用来记录cur_str中的所有字符，而是遍历到当前位置cur_index后之前所有s中出现过的字符及其距离cur_index最近的下标。这样就要求我们不能随意更新cur_str的开始位置start_index，这时，我们更新start_index不仅需要当前字符在index_dict中出现过，位置为prev_index，而且需要保证出现的位置在cur_str中，这就要求上次出现位置prev_index<当前字符串的开始位置cur_index，省去了删除字典元素的步骤。

class Solution(object):
    def lengthOfLongestSubstring(self, s):

        if s is None or len(s) == 0:
            return 0

        max_len = start_index = 0
        index_dict = {}

        for cur_index in range(len(s)):
            cur_str = s[cur_index]
            if cur_str in index_dict and index_dict[cur_str] >= start_index:
                start_index = index_dict[cur_str] + 1
            cur_len = cur_index - start_index + 1
            index_dict[cur_str] = cur_index
            max_len = max(max_len, cur_len)
        return max_len

代码通过时间88ms，这也是网上广泛采用的方法。

如有任何疑问，欢迎评论区留言。