Longest Substring Without Repeating Characters

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

Example

For example, the longest substring without repeating letters for"abcabcbb"is"abc", which the length is3.

For"bbbbb"the longest substring is"b", with the length of1.

分析

前向型指针，子串子数组看成一个窗口满足某个条件，用hash，char做Index 256。while出来后要更新i状态。

1. visit 数组 cs[char] 而不是 char-'a'， 且数组长度是256，是为了防止特殊字符的出现

2. 长度是j-i 不是J-i+ 1

3. 开始不需要cs[s.charAt[i]] ++ 直接设置J就好

4. 模板很重要

答案

模板： cnt记录repeating char的数目，所以是while cnt > 0

#注意进出counter while的几个条件

import collections


class Solution:
    """
    @param s: a string
    @return: an integer
    """
    def lengthOfLongestSubstring(self, s):
        # write your code here
        counter=start=end=d=0
        map = collections.defaultdict(int)
        n = len(s)
        while end<n:
            if map[s[end]] > 0:
                counter+=1
            map[s[end]]+=1
            end+=1
            while counter>0:
                if map[s[start]]>1:
                    counter -=1
                map[s[start]] -=1
                start+=1
            d=max(d,end-start)
        return d

public int lengthOfLongestSubstring(String s) {
        // write your code here
        int[] cs = new int[256];
        int n = s.length();
        int ret = 0;
        for(int i = 0, j = 0; i < n; i ++){
            while(j < n & cs[s.charAt(j)] == 0){
                cs[s.charAt(j)]++;
                j ++;
            }
            ret = Math.max(ret, j - i);
            cs[s.charAt(i)] = 0;
        }
        return ret;
    }

不用Map计算counter，用set也行

class Solution:
    """
    @param s: a string
    @return: an integer
    """
    def lengthOfLongestSubstring(self, s):
        unique_chars = set([])
        j = 0
        n = len(s)
        longest = 0
        for i in range(n):
            while j < n and s[j] not in unique_chars:
                unique_chars.add(s[j])
                j += 1
            longest = max(longest, j - i)
            unique_chars.remove(s[i])

        return longest

loop start,比较上面的loop end

import collections


class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        n = len(s)
        map = collections.defaultdict(int)
        end = d =0
        for start in range(n):
            while end < n and map[s[end]]==0:
                map[s[end]] += 1
                end+=1
            d = max(d,end-start)
            map[s[start]] -= 1
        return d