这篇文章主要介绍了LeetCode如何找出最长不含重复字符的子字符串,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
O(N*C)
(C 是字符的种类数目, 因为找到重复就会停下来, 所以不是 N^2), 不是很优start <= dup < end
[start+1, dup]
中的任一下标作为起点的字符串肯定都会在 end 处停下来, 因为找到了重复的(end 和 dup), 而且这些子字符串长度必然小于以 start 为起点的class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 滑动窗口+当前字符集合, 时刻更新res
start = 0
res = 0
v = set()
for end in range(len(s)):
c = s[end]
if c in v:
# 发现重复了, start向后遍历找dup下标(即上一个c的下标)
while start < end and s[start] != c:
v.remove(s[start])
start += 1
# 此时dup = start, 需要将dup+1作为新的起点
start += 1
else:
# 没有重复, 将当前字符加入字符集合中
v.add(c)
# 最大子字符串长度就是最大的字符集合的长度, 当然此处也可以用end-start+1代替
res = max(res, len(v))
return res
感谢你能够认真阅读完这篇文章,希望小编分享的“LeetCode如何找出最长不含重复字符的子字符串”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。