Lintcode 384. Longest Substring Without Repeating Characters

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

Example

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The longest substring is "abc".

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The longest substring is "b".

Challenge

time complexity O(n)

Code (Java):

public class Solution {
    /**
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int[] count = new int[256];
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            count[c]++;
            
            // shrink left pointer
            //
            while (count[c] > 1) {
                count[s.charAt(left)]--;
                left++;
            }
            
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
        
    }
}