给定一个字符串 s ,请你找出其中不含有重复字符的最长子串 的长度
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是子串的长度,“pwke” 是一个子序列,不是子串。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
采用滑动窗口法
分析:
'''
i=0
j=0
max=0
abcabcbb
i
j
{
a:1
b:1
}
max=
return max
'''
代码实现
class Solution(object):
def lengthLongest(self, s):
# 定义左右指针
left = 0
right = 0
# 定义最大值
max = 0
# 定义字典,存储当前字符串
window = dict()
# 当右指针滑到头时,结束循环
while right < len(s):
# right指向的字符串位置
current_char = s[right] # 第一次:a
# .setdefault()
# 如果键不存在字典中,将会添加键并将值设为默认值0
window.setdefault(current_char, 0)
window[current_char] += 1 # 相当于把a定义成1
# 往后走1位
right += 1
# 窗口中有重复的字符串时缩小窗口
while window[current_char] > 1:
left_char = s[left]
# i往右移动1位
left += 1
# 更新字典中current_char的数量
window[left_char] -= 1
# 临时获取字符串的长度
window_size = right - left
if window_size > max:
max = window_size
return max
s = "pwwkew"
solution = Solution()
res = solution.lengthLongest(s)
print(res)