Longest Substring Without Repeating Characters - Lintcode

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

For"bbbbb"the longest substring is"b", with the length of1.

Analysis

O(n^2) solution is trivial. The O(n) solution is possible. The take away is how to represent the characters using integer arrays. Using hashset should also be ok.

int[] map = new int[256];

Note that the inner while only stops when it's the end of the array or map[s.charAt(j)] == 0) condition is not satisfied. map[s.charAt(i)] = 0; is key to make it possible to continue.

Solution

public int lengthOfLongestSubstring(String s){
    if (s == null || s.length() == 0){
        return 0;
    }

    if (s.length() == 1){
        return 1;
    }

    int length = 0;
    int[] map = new int[256];
    int j = 0;
    for (int i = 0; i < s.length(); i++){
        while (j < s.length() && map[s.charAt(j)] == 0){
            map[s.charAt(j)] = 1;
            j++;
            length = Math.max(length,  j - i);
        }

        if (j == s.length()){
            break;
        }

        map[s.charAt(i)] = 0;
    }

    return length;
}