3. Longest Substring Without Repeating Characters LeetCode Java

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Solution:
2 solutions:
1.O(n^2) time and constant space.
I use two pointers i and j to track the longest substring. Each time when j pointer move forward, check if there exist a same char with s.charAt(j) from i to j-1, if no, j moves forward one more position, otherwise,  i moves to next position where the duplicate char occurs and j moves forward one position as well. During this process update the maximum length by calculating the difference of two pointers.

   public int lengthOfLongestSubstring(String s) {  
     if(s==null || s.length()==0) return 0;  
     int i=0;  
     int j=1;  
     int maxL=1;  
     while(j<s.length()){  
       for(int k=i;k<j;k++){  
         if(s.charAt(k)==s.charAt(j)){  
           i=k+1;  
           break;  
         }  
       }  
       maxL=Math.max(maxL,j-i+1);  
       j++;  
     }  
     return maxL;  
   }  

2.O(n) time and O(n) space.
This solution also use two pointers. The difference is following:
Solution 1 use iteration to check if there is a repeating char between i and j-1, this solution use a HashSet to track all the chars that between i and j-1, because look-up a hashset only cost O(1) time and both i and j only iterate the string once, so the overall time complexity is improved to O(n). So it is time-space trade off.

  public int lengthOfLongestSubstring(String s) {  
     if(s==null || s.length()==0) return 0;  
     int i=0;  
     int j=1;  
     int maxL=1;  
     HashSet<Character> maxSub=new HashSet<Character>();  
     maxSub.add(s.charAt(0));  
     while(j<s.length()){  
       if(!maxSub.add(s.charAt(j))){  
         while(i<j){  
           if(s.charAt(i)!=s.charAt(j)) maxSub.remove(s.charAt(i++));  
           else {  
             i++;  
             break;  
           }  
         }  
       }  
       maxL=Math.max(maxL,j-i+1);  
       j++;  
     }  
     return maxL;  
   }