MyNote
0%

在滑动窗口中做记录 Longest Substring Without Repeating Characters

Posted on Edited on In

在滑动窗口中做记录 Longest Substring Without Repeating Characters

LeetCode 3

在一个字符串中寻找没有重复字母的最长子串

——如”abcabcbb”，则结果为”abc”

——如“bbbbb”，则结果为”b“

——如”pwwkew”，则结果为”wke”

解题步骤

s[i...j]构成了一个滑动窗口

图1

如果j+1所指的字符，在当前这个子字符串中不存在(没有重复的元素)，则j向前滑动，并把其所指字符纳入子字符串中

图2

直到j+1遇到一个字符，是在子字符串中出现过的重复字符。此时j停止滑动，记录下当前的长度，更新结果

图3

此时i，向前滑动直到窗口内，没有重复的字符。此时，j又可以继续向前滑动

图4

代码实现。

借助了visited来判断是否有重复的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lengthOfLongestSubstring(s):
    if not s: 
        return 0
    
    i,j = 0,-1
    s = list(s)
    visited = []
    res = 1  #字符串不为空时，至少有1个
    while i<len(s):
        if j+1<len(s) and s[j+1] not in visited:
            j+=1
            visited.append(s[j])
        else: #在visited有这个元素
            visited.pop(0) #删除左边元素
            i +=1
        
        #结果的保存和更新
        if len(visited)>1:
           # res = max(res,len(visited))
            res = max(res,j-i+1)
    
    return res