Longest Substring without Repeating Characters

题目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

解题方法

这种类型的题目是 hashtable + two pointers的结合

左右两个指针p1,p2, p1是window的左边界,p2是window的右边界。当左边界不动时， 右边界不断向前扩展直到不能满足条件，这时候左边界就往前推进，删掉最左边的元素。

这就是基本的sliding window的思想。

这里要没有重复元素，那么最简单的就是用hashtable来判断是否出现过。

Solution

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length = len(s)
        hashMap = {}
        p1 = 0
        p2 = 0
        maxLength = 0
        while p1 < length:
            while p2 < length and (s[p2] not in hashMap or hashMap[s[p2]] == False):
                hashMap[s[p2]] = True
                curLength = p2 - p1 + 1
                maxLength = max(curLength, maxLength)
                p2 += 1
            hashMap[s[p1]] = False
            p1 += 1

        return maxLength

Reference