[HashTable][Two pointers] Longest Substring Without Repeating Characters

1.Example
/* 

    index         0 1 2 3 4 5 6 7 8 9 10 11 

                      q p x r  j x  k l  t  z  y   x 

1st round       |              |

2nd round               |                          | 

3rd round                         |                 | 

*/

s="abcabcbb" => longest substring  is "abc", whose length is 3

s="bbbb"=> longest substring is "b", whose length is 1


2. Implementation
Q1: substring ?
A1: substring(0,i), subtring (1,i+1),...
Q1: repeating ?
A1; abca X, cannot have the same letter, .contains(letter),
set.add()=>true, DP[i] = DP[i-1]+1
set.add()=>false,DP[i] = DP[i-1];
DP[i] longest length so far
abcabcbb
a
ab
abc
abcaX
1231
abcabs
1231
abcabcdd=>"abcd"
abcad=>"bcad"

"abcdef"
f!=a, e!=b,c!=d
"abcabcbb"
a!=b,b==b,
Q1: all substring O(n^2), sorted by length O(nlogn), find the one without repeating character O(n)
A1:n^2
Q1: when find the repeated character, how to calculate longest

// O(n^3) total number of substrings n*(n+1)/2 and O(n) for check length and no repeated character
// O(n^2) , sort
// Time:O(n)

public int lengthOfLongestSubstring(String s)
{
     



       //validate the input
       if ( s == null || s.length() == 0 )
            return 0;

      
       

     /*
    index      0 1 2 3 4 5 6 7 8 9 10 11
               q p x r j x k l t z  y  x
    1st round  |         |
    2nd round        |                 |
    3rd round              |           |
    */

    HashMap map = new HashMap();
    int max = 0; 
    int runner = 0;
    int walker = 0;
    for (; runner < s.length();runner++)
    {
        char c = s.charAt(runner);
        if (  map.containsKey(c)  )
        {
            // Input:"abba"
            // Output:3
            // Expected:2
            // a[3] repeat a[0] BUT walker is on b[2]
            walker = Math.max(walker, map.get(c)+1);
            map.put(c,runner);
        }
        else 
        {
            map.put(c,runner);
        }
        max = Math.max(runner-walker+1, max);
    }

    return max;



       
}

3. Similar Ones
(H) Longest Substring with At Most Two distinct characters