[LeetCode题解] 3. Longest Substrin

原题：3. Longest Substring Without Repeating Characters
使用了跟76. Minimum Window Substring 一样的模板来做这道题。
还是用数组来track字符的occurrence，然后先挪动右指针，再挪动左指针直到子串中没有重复字符。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] chars = new int[128];
        int maxLen = 0;
        int left = 0;
        int right = 0;
        int counter = 0;
        while (right < s.length()) {
            char rightCh = s.charAt(right);
            if (chars[rightCh] > 0) {
                counter++;
            }
            chars[rightCh]++;
            right++;
            
            while (counter > 0) {
                char leftCh = s.charAt(left);
                if (chars[leftCh] > 1) {
                    counter--;
                }
                chars[leftCh]--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        
        return maxLen;
    }
}

再写一次模板就当加深自己的印象吧：

int findSubstring(string s){
        int[] map = new int[128];
        int counter; // check whether the substring is valid
        int left=0, right=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the char map here */ }

        while(right<s.size()){
            char rightCh = s.charAt(right);
            if(map[rightCh] ?){  /* modify counter here */ }
            map[rightCh]--; // or ++, depends
            right++;

            while(/* counter condition */){ 
                 /* update d here if finding minimum*/
                //increase begin to make it invalid/valid again
                char leftCh = s.charAt(left);
                if(map[leftCh]++ ?){ /*modify counter here*/ }
                map[leftCh]++; // or --, depends
                left++;
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }