☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Longest Substring Without Repeating Characters

Medium TUF ID 929 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, return the length of the longest substring in which no character appears more than once. A substring is a contiguous block of characters; picking characters from different places does not count.

Constraints: 0 ≤ |s| ≤ 5 × 10^4. The string may contain English letters, digits, symbols and spaces, and a space is a character like any other.

Example 1

s = "abcabcbb"
answer = 3          // "abc" (several other windows of length 3 also work)

Example 2

s = "pwwkew"
answer = 3          // "wke"; "pwke" has distinct letters but is not contiguous

Example 3

s = ""
answer = 0          // no characters, so the longest valid substring is empty

Approach 1: Brute force

Intuition. Try every starting index i and extend the substring to the right one character at a time, keeping the characters seen so far in a set. The first time we meet a character already in the set, we can stop extending from this start: every longer substring beginning at i contains that same repeated pair, so none of them can be valid. The longest clean extension over all starts is the answer.

This already improves on the most naive idea, which would list all O(n^2) substrings and check each one in O(n), for O(n^3) in total.

Algorithm.

  1. For each start i: create an empty set.
  2. For each j from i: if s[j] is already in the set, stop; otherwise add it and update best with j - i + 1.
  3. Return best.
static int bruteForce(String s) {
    int n = s.length(), best = 0;
    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;   // s[j] already in s[i..j-1]: every longer substring repeats too
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2) in general. There is a finer bound: the inner loop can never run for more than Σ + 1 steps, where Σ is the alphabet size, because after Σ distinct characters the next one must repeat. So the time is O(n × min(n, Σ)). Space O(min(n, Σ)) for the set.

The weakness is that after a repeat we throw away everything we learned and restart from i + 1, re-adding characters we had just checked.

Approach 2: Better, sliding window with a set

Intuition. Keep a window s[left..right] that is always free of repeats, together with a set of its characters. Move right forward one step at a time. If the new character c is not in the window, simply add it. If it is, the window has to lose its older copy of c; the only way to remove a character from a contiguous window is from the left, so we drop characters from the left until c is gone.

Why is this correct? For every right, the loop leaves left at the smallest index for which s[left..right] has no repeats, so the window is the longest valid substring ending at right. The overall answer is the longest of those. And left never needs to move back: if s[l..right] contains a repeat, so does s[l..right + 1], which contains it.

Algorithm.

  1. Start with an empty set, left = 0, best = 0.
  2. For each right: while s[right] is in the set, remove s[left] and do left++.
  3. Add s[right] to the set and update best with right - left + 1.
  4. Return best.
static int better(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (window.contains(c)) {             // shrink until the old copy of c has left the window
            window.remove(s.charAt(left));
            left++;
        }
        window.add(c);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Complexity. Time O(n): each index is added to the set once and removed at most once, so there are at most 2n set operations in total, even though there is a while loop inside the for loop. Space O(min(n, Σ)).

Approach 3: Optimal, jump the left edge with last-seen indices

Intuition. In Approach 2, when s[right] repeats, left walks forward one character at a time until it passes the previous copy. If we remember where that previous copy is, we can jump there in one step. So store, for each character, the index of its most recent occurrence. When s[right] = c was last seen at prev, the new window must start at prev + 1.

There is one trap. The map is never cleaned, so it still holds indices of characters that have already left the window. Such a stale index is smaller than left, and jumping to it would move left backwards and bring repeats back into the window. So we only jump when prev >= left, that is, when the old copy is really inside the window.

Algorithm.

  1. Start with an empty map last, left = 0, best = 0.
  2. For each right, with c = s[right]:
    • If last has c at index prev and prev >= left, set left = prev + 1.
    • Store last[c] = right.
    • Update best with right - left + 1.
  3. Return best.
static int optimal(String s) {
    Map<Character, Integer> last = new HashMap<>();   // character -> index of its latest occurrence
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer prev = last.get(c);
        if (prev != null && prev >= left) left = prev + 1;   // jump past the old copy; never move left backwards
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry run on s = "abba", the classic case for the stale-index trap:

right c prev prev ≥ left? left after window best
0 a - - 0 “a” 1
1 b - - 0 “ab” 2
2 b 1 yes 2 “b” 2
3 a 0 no, stale 2 “ba” 2

At right = 3, the stored index of a is 0, but the window already starts at 2. Setting left = prev + 1 = 1 would produce the window "bba" and the wrong answer 3. The guard keeps the answer at 2. An equivalent way to write the update is left = Math.max(left, prev + 1).

Complexity. Time O(n): exactly n iterations, each with a constant number of map operations. Space O(min(n, Σ)) for the map.

Approaches 2 and 3 have the same big-O; the difference is that 3 does one step per character instead of up to two. For a known small alphabet, replacing the HashMap with an int[128] (or int[256]) array filled with -1 makes both faster in practice by avoiding boxing; the map version shown here works for any char.

Edge cases and pitfalls