Given a string, find the length of the longest substring without repeating characters.

Example

• 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.

思路

• Hashtable：for character occurrence。int[256]全部初始化为1

• Two Pointers: one points to the first character of a substring, and the other one points to the last character of the substring.

  1. 当发现双指针之间的没有重复的字符时，右指针右移，加入一个字母，int[256]对应位置-1。判断：int[256]是否存在-1，不存在，说明没有重复字符，更新maxLen 且 右指针继续右移。
  2. 当发现双指针之间的有重复的字符时，左指针右移，移除一个字符，int[256]对应位置+1。判断：int[256]是否存在-1，存在，则继续右移左指针，直到不存在重复为止。

  3. 重复以上过程，直到遍历完成。

     
     
     image.png

• 需一个global变量maxLen，记录当前不重复字母substring的最长值。

Time: O(n), Space: O(1)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = Integer.MIN_VALUE;
        int sLen = s.length();
        if (sLen == 0)
        {
            return 0;
        }
        
        int[] tracker = new int [256];
        Arrays.fill (tracker, 1);
        
        int left = 0;
        int right = 0;
        
        while (right < sLen)
        {
            tracker [s.charAt(right)] --;
            if (!hasNegativeEntry (tracker))
            {
                int len = right - left + 1;
                maxLen = Math.max(len, maxLen);
            }
            
            while (hasNegativeEntry (tracker))
            {
                tracker [s.charAt(left)] ++;
                left++;
            }

            right ++;
        }
        
        return maxLen;
    }
    
    public boolean hasNegativeEntry (int[] tracker)
    {
        for (int entry : tracker)
        {
            if (entry < 0)
            {
                return true;
            }
        }
        
        return false;
    }
}