LeetCode-3.无重复字符的最长子串

Author Avatar
xffish 11月 11, 2018
  • 在其它设备中阅读本文章

LeetCode-3.无重复字符的最长子串

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。

请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

英文原文:
Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

我的解答:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = max_len = 0
        used = {}

        for i, item in enumerate(s):
            if item in used and start <= used[item]:
                start = used[item] + 1
            else:
                max_len = max(max_len, i - start + 1)
            used[item] = i

        return max_len

This blog is under a 知识共享许可协议
本作品采用知识共享署名 4.0 国际许可协议进行许可

本文链接:https://www.xffish.xyz/2018/11/11/LeetCode-3-无重复字符的最长子串/