LeetCode-3. Longest Substring Without Repeating Characters

[ninehills]

20170715

题目

https://leetcode.com/problems/longest-substring-without-repeating-characters

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.

思路

本题刚开始没有想到有效的思路，只好看了下别人的实现，思路是『滑动窗口』：

顺序遍历字符串

• 如果字符已经出现过并且substring的起点在重复字符（含）之前，更新substring的起点到重复字符的后一位
• 其他情况下，用当前substring的长度和保存的max长度取max

解答

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        used = {}
        start = max_length = 0
        for index,value in enumerate(s):
            if value in used and start <= used[value]:
                start = used[value] + 1
            else:
                max_length = max(max_length, index - start + 1)
            used[value] = index
        return max_length
# 3
print Solution().lengthOfLongestSubstring("pwwkew")