Longest Substring Without Repeating Characters

Question (LC.3)

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

Example

I: "abcabcbb"
O: 3 because "abc"
I: "bbbbb"
O: 1 because "b"
I: "pwwkew"
O: 3 because "kew"

Analysis

The brute force approach is to try all substrings.

Brute Force

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    Set<Character> noRepeat = new HashSet<>();
    int maxLength = Integer.MIN_VALUE;

    for (int i = 0; i < s.length(); i++) {
        noRepeat.clear();
        for (int j = i; j < s.length(); j++) {
            if (noRepeat.contains(s.charAt(j))) {
                break;
            }
            noRepeat.add(s.charAt(j));
        }
        maxLength = Math.max(maxLength, noRepeat.size());
    }
    return maxLength;
}

Optimization

Again, j doesn't have to go back to i after find each non-repeating substring. We can shrink then extend the current non-repeating substring.

S   p  w  w  k  e  w
L1  i->j
L2     i(j)
L3        i->j
L4        i---->j
L5           i----->j
L6               i->j

Optimized Code

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    Set<Character> noRepeat = new HashSet<>();
    int maxLength = Integer.MIN_VALUE;
    int j = 0;
    for (int i = 0; i < s.length(); i++) {
        // extend
        while (j < s.length() && noRepeat.add(s.charAt(j))) {
            j++;
        }
        maxLength = Math.max(maxLength, noRepeat.size());
        // shrink
        noRepeat.remove(s.charAt(i));
    }
    return maxLength;
}