Leetcode/各大家 -- 3. Longest Substring Without Repeating Characters(Window 2 ptr)

3. Longest Substring Without Repeating Characters
Medium
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.

 Amazon Adobe Bloomberg Yelp

思路1： Using window, counter to track duplicates in string. adjust window when find repeats. When pass a char in window, decrease its count since the new valid substring won't contains current char.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        int counter = 0, len = 0;
        while(end < s.length()){
            char cur = s.charAt(end);
            if(!map.containsKey(cur)) map.put(cur, 0);
            map.put(cur, map.get(cur) + 1);
            if(map.get(cur) > 1) counter++;//substr contains repeats
            while(counter > 0){//just case of 2 repeating char in substr
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) - 1);
                if(map.get(c2) > 0) counter--;
                start++;
            }
            len = Math.max(end - start + 1, len);
            end++;
        }
        return len;
    }
}

参考： https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation
思路2： Create a HashMap to store <character, last occurrence position>
            Two pointer: i (right) iterate string;
            j (left) track the position of last dup char. (only move forward so maintain get the max of j)
            eg: a(j=0)b(j=1)b(j=2)a(j=2) so i = 3 , j =2, len = 3 - 2 + 1 = 2 
            max: the max length i-j+1
Complexity: Time O(1) HashMap O(N)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0,j =0;//j is left pointer -to pos of last occurrence of the dup char
        for (int i=0; i<s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);//only move forward(max),else eg: abba, last a: 3=3(i)-(0+1)(j) + 1
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}