P12 无重复字符的最长子串 LeetCode3

P12 无重复字符的最长子串，难度中等。

题目

English

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

中文

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

示例 1:

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

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

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

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

---

解题

伪代码描述（推荐）

---

解题和源码

Python代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        StartIndex = 0
        MaxLength = 0
        UsedDict = {}
        for index, char in enumerate(s):
            if char in UsedDict and StartIndex <= UsedDict[char]:
                StartIndex = UsedDict[char] + 1
            else:
                if index-StartIndex+1>MaxLength:
                    MaxLength = index-StartIndex+1
            UsedDict[char] = index
        return MaxLength

执行结果：

执行用时 :24 ms, 在所有 python 提交中击败了99.91%的用户

内存消耗 :12.1 MB, 在所有 python 提交中击败了39.47%的用户

本文作者： Yao Zhu
发布时间： 2019-12-21
最后更新： 2019-12-21
本文链接： https://juoyo.github.io/posts/a627a612.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信