Leetcode(3) Longest Substring Without Repeating Characters

Description:

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(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = [];
        for i in range(len(s)):
            r = s[i];
            cnt = 1;
            j = i + 1;
            while (j < len(s)):
                if (s[j] not in r):
                    r += s[j];
                    cnt+=1;
                    j+=1;
                else:
                    break;
            count.append(cnt);
        if(len(count) == 0):
            return 0;
        maxcnt = max(count);
        index = count.index(maxcnt);
        return maxcnt;

采用滑动窗格法：

用一个数据结构记录序列中存在的字符，考虑i与j两个指针之间的子串长度，若[i,j)为序列且s[j]不存在于此序列中，则s[j]加入字符集，j指针右移；否则i指针右移，且将s[i]移出字符集（此处存在优化，即i不必一次次右移，直接移至序列中与s[j]相同的字母的下一个即可），给出未优化的滑动窗格法代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0;j = 0; ans = 0;list = [];
        while(i<len(s) and j <len(s)):
            if(s[j] not in list):
                list.append(s[j]);
                ans = max(ans,j - i + 1);
                j+=1;
            else:
                list.remove(s[i]);
                i+=1;
        return ans;