Demo: solving a problem with a sliding window

Written Explanation

Step 1: state the problem exactly

A substring is a block of consecutive characters. So "abc" is a substring of "abcabcbb", but "acb" is not (it is a subsequence, not consecutive). We want the length of the longest one with all characters different.

Write examples before code:

"pwwkew" is a good trap: "pwke" has four distinct letters, but it is not consecutive, so it does not count.

Step 2: the brute-force idea

Try every starting position. From each start, extend to the right, remembering characters in a set, until you meet a character that is already in the set. Record the length, then try the next start.

static int brute(String s) {
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (!seen.add(s.charAt(j))) break;      // add returns false if already present
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

The Set.add method returns false when the element is already present (the HashSet documentation says so), which gives us a neat way to detect a repeat. This brute force is O(n²) in the worst case: a nested loop over start and end. An even simpler version that checks every substring separately and tests each one for repeats is O(n³). We keep this method, because later it works as a trusted checker for the fast version.

The waste: when the window from start 0 is "abc" and a repeated a stops it, the next start (1) rebuilds "bc" from scratch, even though we already knew those characters were fine.

Step 3: design the window

Use a window [left, right] that always contains no repeated character, and a Set<Character> holding exactly the characters inside it.

Each step of the loop:

1. Look at the new character c = s.charAt(right).
2. While c is already in the set, remove s.charAt(left) from the set and move left forward. This shrinks the window from the left until c no longer repeats.
3. Add c to the set. The window [left, right] is valid again.
4. The window length is right - left + 1; update the best.

Step 2 needs while, not if: the repeated character may be several positions back, so one removal may not be enough.

Step 4: write it, with the planned mistake

First, the version with the length written the wrong way:

static int buggy(String s) {
    Set<Character> w = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        while (w.contains(s.charAt(right))) { w.remove(s.charAt(left)); left++; }
        w.add(s.charAt(right));
        best = Math.max(best, right - left);      // BUG: length is missing + 1
    }
    return best;
}

Test it on "abc", where we know the answer is 3:

System.out.println(buggy("abc"));

Output:

2

Wrong. Trace it: when right = 2, left = 0, the window is a, b, c: three items, but right - left is 2. Both ends are included, so the number of items is right - left + 1. A one-item window (left == right) shows the problem most simply: right - left says 0.

The fix:

static int longest(String s) {
    Set<Character> w = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        while (w.contains(s.charAt(right))) { w.remove(s.charAt(left)); left++; }
        w.add(s.charAt(right));
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Step 5: test edge cases and compare with brute force

I ran longest and brute on several inputs, printing both results:

"abc" -> 3 brute 3
"" -> 0 brute 0
"aaaa" -> 1 brute 1
"abcabcbb" -> 3 brute 3
"pwwkew" -> 3 brute 3
"abba" -> 2 brute 2

The empty string works because the loop never runs and best stays 0. "aaaa" works because each new a removes the previous one. "abba" is a great test: when the second a arrives, the window is "b" (the first a was already dropped while handling the second b), and the set correctly does not contain a any more.

Step 6: state the cost

Each character enters the window once (add) and leaves at most once (remove), and both pointers only move forward. That is at most about 2n moves, so the time is O(n), assuming the HashSet operations take constant time on average, which the Java documentation states for a well-spread hash function. The set holds at most as many characters as the window, and never more than the number of distinct characters in the string, so the space is O(k) where k is the size of the character set that can appear (O(min(n, k))).

Step 7: why a window, and not another technique?

Recognizing the technique is part of the skill. Ask these questions in order:

Here the answer is a consecutive block, and the rule ("no repeated character") can be updated one character at a time, so a window fits. The data is not sorted, which rules out two pointers.