A session-token checker, a SKU-code validator, and a request-ID stream all ask the same question: what is the longest contiguous stretch with no repeated character? The first version nested a restart: for each start i, grow j until a character repeats, throw the set away, begin again at i + 1. A dozen-character SKU returned instantly. A log of request IDs was still rebuilding windows when the request timed out.

Return the length of the longest contiguous substring whose characters are all unique. A string already gives s.charAt(i) for free. Nested uniqueness uses that and still pays O(n²).

This is an interview writeup, not a sliding-window lecture. The sliding window post owns grow and shrink. Here we only care about when the left edge jumps because a character repeated.

The problem

Given a String s, return the length of the longest contiguous substring with all unique characters. The empty string is length 0.

s = "abcabcbb"  →  3   ("abc")
s = "bbbbb"     →  1   ("b")
s = "pwwkew"    →  3   ("wke")
s = ""          →  0

Note: "wke" is a substring of "pwwkew". "pwke" is a subsequence. This prompt wants a contiguous stretch.

Nested uniqueness is the honest brute force

For every start i, grow j until a character in [i..j] repeats. Rebuild a set on each inner step. Correct. Quadratic.

int lengthNested(String s) {
    int best = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < n; j++) {
            if (!seen.add(s.charAt(j))) {
                break;
            }
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

At n = 20 this is a rounding error. At a long request-ID stream you paid a nested scan for a question a window answers in one pass: if this character is already in the window, jump left past its previous occurrence.

Right grows; left jumps past the repeat

Two indexes, both only forward. right is the next character that wants in. If it is new, the window grows. If it already sits in the window, left moves to one past the earlier copy so the window is unique again. You never restart from 0.

Keep a hash table of character → last index seen. When you look up s.charAt(right):

  • Miss: the character is new. Record right.
  • Hit: left = Math.max(left, prev + 1). Then record right.

Then best = max(best, right - left + 1). Walk "abcabcbb":

s = a b c a b c b b
    0 1 2 3 4 5 6 7

right=0 c=a  last {}           left=0           window [a]     best=1
right=1 c=b  last {a:0}        left=0           window [ab]    best=2
right=2 c=c  last {a:0,b:1}    left=0           window [abc]   best=3
right=3 c=a  last {a:0,...}    left=max(0,1)=1  window [bca]   best=3
right=4 c=b  last {b:1,...}    left=max(1,2)=2  window [cab]   best=3
right=5 c=c  last {c:2,...}    left=max(2,3)=3  window [abc]   best=3
right=6 c=b  last {b:4,...}    left=max(3,5)=5  window [cb]    best=3
right=7 c=b  last {b:6,...}    left=max(5,7)=7  window [b]     best=3

The Java is that walk:

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int left = 0;
    int best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer prev = last.get(c);
        if (prev != null) {
            left = Math.max(left, prev + 1);
        }
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Time is O(n) — one pass, one expected-O(1) lookup and put per index. Space is O(min(n, alphabet)) for the map. Empty input never enters the loop; best stays 0.

Note: A Set plus while (window.contains(c)) { remove s[left]; left++; } is the same linear bill: each index is dropped at most once. Last-index is the jump, not a shrink-one-by-one. Without Math.max, a stale index left of the window yanks left backward. "abba": after the second b, left is 2. The second a still has last-index 0. left = 0 + 1 would walk backward; Math.max(2, 1) keeps left at 2.

What interviewers usually poke next

  • Return the substring, not the length. Keep a pair of best endpoints while you already compute right - left + 1. Same pass.
  • Set vs last-index. Both O(n). Set shrinks one character at a time; last-index jumps. Say why Math.max is required on the jump.
  • ASCII vs Unicode. int[128] (or int[256]) of last indexes is legal if the alphabet is bounded; initialize to -1. A map is the honest default for Java char.
  • Later window family. Longest repeating character replacement and minimum window substring reuse grow/shrink with different invariants. Do not solve them here.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why nested uniqueness is correct, why left jumps past the previous occurrence instead of restarting at 0, and why Math.max keeps a stale last-index from yanking left backward.