社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
示例 4:
输入: s = “”
输出: 0
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
典型的滑动窗口问题.
窗口长度取当前最大子串长度
在滑动过程中检测窗口内部是否符合条件(没有重复字符)
题解图示:
# 作者: 爱编程的章老师
# 主题:LeetCode题解
# day03
'''
给定一个字符串,找出这个字符串的最长子串的长度
'''
def get_length(s:str):
# 如果字符串是空的,返回0
if not s:
return 0
# 初始位置指针与长度
index = 0
l = 0
# 初始化子串
substr = ""
# 当位置指针+ 长度 = 字符串长度的时候,说明已经检测完毕了
while index + l < len(s):
# 检测要加入的字符串是否在子串,如果在子串中,则将位置指针后移一位.
if s[index + l] in substr:
index += 1
substr = s[index:index + l]
# 检测新的子串有没有重复的字符,如果有就向后移动指针,直到全部不复为止
while len(substr) > len(set(substr)):
index += 1
substr = s[index:index + l]
# 如果要加入的字符串没有在子串,就将长度增加一,并更新子串
else:
l += 1
substr = s[index:index + l]
return l
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!