Longest Substring without Repeating Characters

Evey time revisiting this problem, there will be slightly different solution coming up. not always more optimized, many times, new solution is worse than old ones. I need to remember the best solution to this one, not only because it is so elegant, but also because of the common use of character array, or hash table.

Here is an old version of solution, similar to the ones provided by leetcode, but thinking reversely, the moving cursor.

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution {     public int lengthOfLongestSubstring(String s) {       if(s==null)return -1;     if(s.isEmpty())return 0;     //this set contains only one check's visiting condition     Set<Character> charSet = new HashSet<Character>();     int maxLen=0,h=0,t;String longestStr="";         //having two pointers, one for head adjustment, one for substring tail adjustment     //end of substring is marked by first repeated character     //for character being repeated, its left side positions won't construct longer string     //then current one, so it is safe to start from its next position. that  means, header     // can be moved to next position of character being repeated     while (h<s.length()){         //the inner loop will end when first repeat character is found         //that also marks end of substring currently being checked         //it start from header+number of characters between the repeated characters         t=h+charSet.size();         while(t<s.length() && !charSet.contains(s.charAt(t))){             charSet.add(s.charAt(t));             t++;         }                 maxLen = Math.max(maxLen, charSet.size());         if(t==s.length())break;         if (t-h+1>maxLen)longestStr=s.substring(h,t);         //advance h to character being repeated, removing characters from charSet at same time         //because new string start from right of character being repeated         while(h<s.length() && s.charAt(h)!=s.charAt(t)){             charSet.remove(s.charAt(h));             h++;         }         //move to new substring start position         h++;     }     return maxLen;     } }

This is the one by leetcode:

1  2  3  4  5  6  7  8  9 10 11 12 13

public int lengthOfLongestSubstring(String s) { boolean[] exist = new boolean[256]; int i = 0, maxLen = 0; for (int j = 0; j < s.length(); j++) { while (exist[s.charAt(j)]) { exist[s.charAt(i)] = false; i++; } exist[s.charAt(j)] = true; maxLen = Math.max(j - i + 1, maxLen); } return maxLen; }

And here is a better version with only one pass:

1  2  3  4  5  6  7  8  9 10 11 12 13 14

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