无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

知识点

字符串

---

使用字典存储上一次出现的位置

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        pos=[-1 for i in range(256)]
        left=0
        right=0
        max_length=0
        while right<=len(s)-1:
            if pos[ord(s[right])]<left:
                if max_length<right-left+1:
                    max_length=right-left+1
                pos[ord(s[right])]=right
                right+=1
            else:
                left=pos[ord(s[right])]+1
        return max_length

---

使用数组存储上一次出现的位置

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        pos={}
        left=0
        right=0
        max_length=0
        while right<=len(s)-1:
            if s[right] not in pos or pos[s[right]]<left:
                if max_length<right-left+1:
                    max_length=right-left+1
                pos[s[right]]=right
                right+=1
            else:
                left=pos[s[right]]+1
        return max_length

---

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。