[LeetCode] 3. Longest Substring Without Repeating Characters 题解

问题描述

输入一个字符串,找到其中最长的不重复子串

例1:

输入:"abcabcbb"
输出:3
解释:最长非重复子串为"abc"

例2:

输入:"bbbbb"
输出:1
解释:最长非重复子串为"b"

例3:

输入:"pwwkew"
输出:3
解释:最长非重复子串为"wke"

问题难度

Medium

解题思路

本题采用「滑动窗口法」可以达到较理想的时间复杂度 O(n),滑动窗口指的是当前非重复子串所在的窗口,此滑动窗口有两种操作方法

  1. 检查下一个字符是否会重复,如未重复,则将窗口向右扩大
  2. 发现重复字符,则将窗口右边界保持不变,左边界右移,以此缩小窗口

上面的操作比较容易理解,唯一需要注意的是第 2 点中,当发现重复字符时,窗口左边界向右移动几个单位,我们可以看一个示意图:

+---------+ 
| a b c d | e d x y z 
+---------+
 
+-----------+ 
| a b c d e | d x y z // 未发现重复,向右扩大窗口
+-----------+

        +-----+ 
a b c d | e d | x y z // 发现重复,缩小窗口
        +-----+

假设输入字符串为 "abcdedxyz",一直到我们遍历到字符 e 时,均未发现重复的字符串,至此对窗口进行的操作都是向右扩大,当检查到下一个字符 d 时,由于前面字符串中已经出现过该字符,所以窗口左边界需要进行右移,移动的位置、即新子串窗口的起始点,正好是两个重复字符中、第一个重复字符的右边,如图所示为字符 e 所在的位置。

至此,我们可以开始写程序了:

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxlen = 0
        current_substring = [None]*128
        current_substring_len = 0
        begin_index = 0
        for i in s:
            stoi = ord(i)
            if current_substring[stoi] is None or current_substring[stoi] < begin_index:
                current_substring[stoi] = begin_index + current_substring_len
                current_substring_len += 1
            else:
                if maxlen < current_substring_len:
                    maxlen = current_substring_len 
                
                sub_len = current_substring[stoi] - begin_index + 1
                begin_index = current_substring[stoi] + 1
                current_substring_len -= sub_len

                current_substring[stoi] = current_substring_len + begin_index
                current_substring_len += 1

        if maxlen < current_substring_len:
            maxlen = current_substring_len
        return maxlen

以上代码中,current_substring 是一个缓冲区,用来存放当前子字符串,缓冲区声明为 128 个是为了让数组的下标空间能容纳 128 个 ASCII 字符,即这里用数组的下标来表示字符,这样做的好处是可以很快的知道某个字符是否出现重复,数组的内容我们填的是该字符对应的下标,例如字符串 "abcde" 填到 current_substring 中为:

            index:   0..97  98  99  100 101 ..
                   +---+---+---+---+---+---+---+
current_substring: |...| 0 | 1 | 2 | 3 | 4 |...|
                   +---+---+---+---+---+---+---+

我们用变量 begin_index 来记录当前窗口在字符串中的起始位置,而 current_substring_len 用来记录当前窗口的长度。for 循环是对字符串的遍历。

首先将字符转化为其对应的整数 stoi,检查 stoi 中的内容是否为空,或其存储的位置是否在窗口的左边,如是则表示该字符在 begin_index 之后未出现过,非重复子串可以继续累加。

否则表示出现重复,出现重复时,需要将窗口的左边界右移,或者说对新的滑动窗口进行初始化,实际上只需更新 begin_indexcurrent_substring_len 两个值。

最后,我们需要在每一次窗口改变时,或在结束遍历时,判断当前子字符串的长度是否是最长的,并将最长串存储在 maxlen 中,作为结果返回。

原题链接