3. Longest Substring Without Repeating Characters

1. 题意

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.

2.算法

hashMap<Character,indexOfCharacter>

当找到重复的时候记录non-duplicate substring的起始位置 map.get(c)+1
或者用一个array当作map

   public int lengthOfLongestSubstring(String s) {  
     int[] visited = new int[128];  
     Arrays.fill(visited,-1);  
     int max = 0, begin = 0;  
     for(int i = 0; i <s.length(); i++){  
       char c = s.charAt(i);  
       if(visited[c]==-1||begin > visited[c]){  
         visited[c] = i;  
       }else{  
         max = Math.max(max, i-begin);  
         begin = visited[c]+1;  
         visited[c] = i;  
       }  
     }  
     max = Math.max(max,s.length()-begin);  
     return max;  
   }