DSA-021 · Variable sliding window

Longest Substring Without Repeating Characters

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3286 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the maximum length of a contiguous substring with no repeated UTF-16 code unit. The unit of comparison is Java char, and length uses String.length() units.

s is non-null with 0–100,000 UTF-16 code units. Empty string returns 0; null is outside the contract.
Case, spaces, punctuation, and surrogate halves are distinct char values. This is deliberately not Unicode code-point or grapheme-cluster matching.
Return a length only; preserve the immutable string. A substring must be contiguous.

Examples

Input: "abcabcbb"
Output: 3
"abc" is valid; repeating patterns do not make a longer unique window.
Input: "abba"
Output: 2
After the second b, left becomes 2; the later a must not move it backward.
Input: "pwwkew"
Output: 3
"wke" is a substring, while "pwke" is a subsequence and is invalid here.

Before you start

Contiguous substring versus subsequence
Java UTF-16 char indexing and a last-seen map

Recognize the structure

We extend a contiguous range and repair one precise violation: a repeated symbol. Last-seen positions tell us how far the left boundary must move. A window cannot generally solve arbitrary negative-valued sum constraints, whose validity is not monotone under shrinking.

Try before revealing

Hint 1

Maintain a valid interval rather than restarting each suffix.

Hint 2

Where was the newly appended char last seen?

Hint 3

Jump left past that index only if it is inside the current window.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Restart from each position

For every start, scan right with a fresh set until a duplicate appears. For "aba", start 0 reaches "ab", start 1 reaches "ba", and start 2 reaches "a". This repeats membership work across overlapping windows and can take O(n²) expected time under hashing; each temporary set holds at most u distinct char values.

Improve the baseline

Reuse the valid window

Keep a left boundary and scan right once. Before appending the new char, the old window has no duplicates.

Jump past an in-window occurrence

If its last occurrence is previous, set left=max(left,previous+1). Occurrences before left do not violate the current window.

Update the best length

After repairing left, right-left+1 describes a valid substring. Remember the maximum, then continue without restarting.

Why it is correct

Initialize

left=0 and the empty window are valid; no char has a recorded occurrence.

Preserve

The only possible new duplicate is the char appended at right. Removing through its previous in-window occurrence eliminates that duplicate; all other chars were already distinct. Taking max prevents a stale occurrence from reintroducing old invalid positions.

Optimality and termination

The chosen left is the earliest valid start for each right: any earlier start would retain the duplicate responsible for the latest required boundary. Thus this is the longest valid substring ending at right. Checking every right yields the global optimum in a finite scan.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public final class Solution {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char symbol = s.charAt(right);
            Integer previous = lastSeen.put(symbol, right);
            if (previous != null) left = Math.max(left, previous + 1);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static int baseline(String s) {
        int best = 0;
        for (int start = 0; start < s.length(); start++) {
            Set<Character> seen = new HashSet<>();
            for (int end = start; end < s.length(); end++) {
                if (!seen.add(s.charAt(end))) break;
                best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
}

Read the meaningful blocks

Record the previous position

Map.put returns the old index while storing the current one.

Never move left backward

Math.max(left,previous+1) is essential for cases such as "abba".

Measure after repair

Updating best before removing a duplicate would count an invalid window.

Complexity

Expected O(n) time, with one last-seen lookup/update per char. O(u) auxiliary map entries, where u≤min(n,65,536). Hashing bounds are expected.

The restart baseline can require O(n²) expected work and O(u) workspace. A fixed 65,536-entry index table gives deterministic indexing with a fixed alphabet allocation; a code-point version needs a different representation.

Exact-state walkthroughs

Reveal normal and boundary traces

A stale occurrence must not move left backward

Input: "abba" · Result: 2

Step 1 of 6: Initialize an empty valid window.

No repeated symbol exists in the empty window.

UTF-16 input positions

0: "a"
1: "b"
2: "b"
3: "a"

State after this step
Variable	Value
left	`0`
best	`0`
lastSeen	`[]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.HashSet;
 3 import java.util.Map;
 4 import java.util.Set;
 5 
 6 public final class Solution {
 7     public static int lengthOfLongestSubstring(String s) {
 8         Map<Character, Integer> lastSeen = new HashMap<>();
 9         int left = 0, best = 0;
10         for (int right = 0; right < s.length(); right++) {
11             char symbol = s.charAt(right);
12             Integer previous = lastSeen.put(symbol, right);
13             if (previous != null) left = Math.max(left, previous + 1);
14             best = Math.max(best, right - left + 1);
15         }
16         return best;
17     }
18 
19     public static int baseline(String s) {
20         int best = 0;
21         for (int start = 0; start < s.length(); start++) {
22             Set<Character> seen = new HashSet<>();
23             for (int end = start; end < s.length(); end++) {
24                 if (!seen.add(s.charAt(end))) break;
25                 best = Math.max(best, end - start + 1);
26             }
27         }
28         return best;
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize an empty valid window.
No repeated symbol exists in the empty window.
left
0
best
0
lastSeen
[]
Append "a" and repair the left boundary.
The repaired window is unique and left never decreases.
right
0
symbol
"a"
previous
null
left
0
best
1
window
"a"
lastSeen
[["a",0]]
Append "b" and repair the left boundary.
The repaired window is unique and left never decreases.
right
1
symbol
"b"
previous
null
left
0
best
2
window
"ab"
lastSeen
[["a",0],["b",1]]
Append "b" and repair the left boundary.
The repaired window is unique and left never decreases.
right
2
symbol
"b"
previous
1
left
2
best
2
window
"b"
lastSeen
[["a",0],["b",2]]
Append "a" and repair the left boundary.
The repaired window is unique and left never decreases.
right
3
symbol
"a"
previous
0
left
2
best
2
window
"ba"
lastSeen
[["a",3],["b",2]]
Return the contract result.
The final state satisfies the requested output contract.
result
2

Empty window

Input: "" · Result: 0

Step 1 of 2: Initialize an empty valid window.

No repeated symbol exists in the empty window.

UTF-16 input positions

Empty at this step.

State after this step
Variable	Value
left	`0`
best	`0`
lastSeen	`[]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.HashSet;
 3 import java.util.Map;
 4 import java.util.Set;
 5 
 6 public final class Solution {
 7     public static int lengthOfLongestSubstring(String s) {
 8         Map<Character, Integer> lastSeen = new HashMap<>();
 9         int left = 0, best = 0;
10         for (int right = 0; right < s.length(); right++) {
11             char symbol = s.charAt(right);
12             Integer previous = lastSeen.put(symbol, right);
13             if (previous != null) left = Math.max(left, previous + 1);
14             best = Math.max(best, right - left + 1);
15         }
16         return best;
17     }
18 
19     public static int baseline(String s) {
20         int best = 0;
21         for (int start = 0; start < s.length(); start++) {
22             Set<Character> seen = new HashSet<>();
23             for (int end = start; end < s.length(); end++) {
24                 if (!seen.add(s.charAt(end))) break;
25                 best = Math.max(best, end - start + 1);
26             }
27         }
28         return best;
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize an empty valid window.
No repeated symbol exists in the empty window.
left
0
best
0
lastSeen
[]
Return the contract result.
The final state satisfies the requested output contract.
result
0

Test the contract

Input: ""
Output: 0
Empty.
Input: "bbbbb"
Output: 1
All repeated.
Input: "a b"
Output: 3
Space is a symbol.
Input: "Aa"
Output: 2
Case-sensitive.

Common mistakes and counterexamples

Move left backward

Counterexample: "abba" can incorrectly produce length 3 at the last a.

Use max with the existing left.

Confuse substring with subsequence

Counterexample: "pwwkew" does not contain "pwke" contiguously.

Maintain one continuous interval.

Silently claim Unicode-character semantics

Counterexample: A supplementary symbol occupies two Java chars.

State code-unit semantics or explicitly convert to code points.

Follow-ups

Return the substring itself.

Store bestStart and bestLength. Specify the earliest-start tie policy. Materialize substring once at the end; copying every candidate adds unnecessary work.

Count Unicode code points instead.

Convert to an int[] of code points or iterate codePointAt with offset tracking. Decide whether output length and indices are code-point or UTF-16 units; neither automatically means grapheme clusters.

Allow at most k distinct symbols.

Keep frequencies, increment on entry, decrement while too many distinct symbols remain, and delete zero counts. Last occurrence alone does not express the changed validity rule.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 105/20,000 characters

Self-review

I state the character model.I keep left monotone.I measure only a valid repaired window.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Sliding windows: define validity first

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.