题目描述
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"
,所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"
,所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"
,所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke"
是一个子序列,不是子串。
思路
滑动窗口
1. 遍历字符
2. 窗口的最左侧指的字符从窗口的列表中去掉
3. 窗口的右指针开始循环,循环的条件:rk+1<n and s[rk+1] not in 窗口列表里
4. 循环3结束,取max
5. 返回记录的最大值
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
window = []
rk = -1
ans = 0
for i in range(len(s)):
if i != 0:
window.remove(s[i-1])
while rk+1<len(s) and s[rk+1] not in window:
window.append(s[rk+1])
rk+=1
ans = max(ans,rk-i+1)
return ans
if __name__=='__main__':
s = Solution()
print(s.lengthOfLongestSubstring('pwwkew'))