接外包,有相关需求的可以联系我:Telegram | Email

无重复字符的最长子串

该文章创建(更新)于01/13/2022,请注意文章的时效性!

题目

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

  • 示例 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 由英文字母、数字、符号和空格组成

解题

滑动窗口算法

  • 提交代码
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = []
        max = 0

        while right < len(s):
            window.append(s[right])
            right+=1
            #print("right: " + str(right) + "\tleft: " + str(left))
            #print(window)
            if (max < len(window)):
                max = len(window)

            while(right < len(s) and s[right] in window and left < right):
                window.remove(window[0])
                left += 1

        return max
  • 本地测试代码
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = []
        max = 0


        while right < len(s):
            window.append(s[right])
            right+=1

            # print("right: " + str(right) + "\tleft: " + str(left))

            print(window)

            if (max < len(window)):
                max = len(window)

            while(right < len(s) and s[right] in window and left < right):
                window.remove(window[0])
                left += 1

        return max


S = Solution()

length = S.lengthOfLongestSubstring("abcdda")

print("#########################")
print(length)


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/01/13/longest-substring-without-repeating-characters/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)