3. Longest Substring Without Repeating Characters

Problem:

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.

Analysis:
3/4/2018 update
Since this problem requires to get longest substring, it can be categorized into mamximum siding window problem. Always keep the window valid, and update outside of window update.
------------------------------------------------------------------------------------------------------------------------------------------

2/28/2018 update
The ascii 256 implementation is two tricky not applicable in general. I prefer the hashtable way. Why do we need to check map.get(charAt(i)) and j? cuz there is a special case "abbacedg". When i reaches the second a at pos 3. j is at pos2. We cant go back to pos 0 where the first a at. So we get the larger index of the first occurrence of a and j.

   public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

--------------------------------------------------------------------------------------------------------------------------------------------

It comes natural that use two pointers: i and j. Once found s[j] exists in s.substring(i, j), update max length. Then we can know that, i should start from j'+1. j' is the index of first occurrence of s[j]. We can use ASCII array to store the character's index. 

Solution:

 public class Solution {  
   public int lengthOfLongestSubstring(String s) {  
     int[] chars = new int[256];  
     Arrays.fill(chars, -1);  
     int max = 0;  
     for (int j = 0, i = 0; j < s.length(); j++) {  
       i = Math.max(chars[s.charAt(j)], i);  
       max = Math.max(max, j - i + 1);  
       chars[s.charAt(j)] = j + 1;  
     }  
     return max;  
   }  
 }