☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Longest Substring Without Repeating Characters

Medium TUF ID 2857 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, return the length of the longest substring (a contiguous block of characters) in which no character appears more than once.

Constraints: 0 ≤ |s| ≤ 5 × 10^4; s consists of English letters, digits, symbols and spaces, so every character fits in an extended-ASCII table of 256 entries.

Example 1

s = "abcabcbb"
answer = 3          // "abc"; every longer window contains a repeat

Example 2

s = "pwwkew"
answer = 3          // "wke"; "pwke" is longer but it is a subsequence, not a substring

Example 3

s = "bbbbb"
answer = 1          // every window of length 2 is "bb"

Approach 1: Brute force

Intuition. Every substring has a starting index. Fix the start i and keep extending the end j to the right while the characters stay distinct. The moment a character repeats, every longer substring that starts at i also contains that repeat, so there is no point continuing; break and move to the next start. A 256-entry boolean array tells us in constant time whether a character is already inside s[i..j].

Algorithm.

  1. For every start i, create a fresh seen array.
  2. For j = i, i + 1, ...: if s[j] is already seen, stop this start. Otherwise mark 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++) {
        boolean[] seen = new boolean[256];
        for (int j = i; j < n; j++) {
            char c = s.charAt(j);
            if (seen[c]) break;                    // s[i..j] would contain c twice
            seen[c] = true;
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2) in the worst case: for each of the n starts the inner loop can run up to n steps (it actually stops after at most 257 steps because of the pigeonhole principle, so the true bound is O(n · min(n, 256))). Space O(1): the 256-entry array does not grow with n.

The waste is clear when you look at "abcdefa": from start 0 we learn that "abcdef" is clean, then from start 1 we re-check "bcdef" all over again. The next approaches keep that knowledge.

Approach 2: Better, sliding window with a set

Intuition. Keep a window s[l..r] that is always repeat-free, and a set holding exactly the characters inside it. Move r one step at a time. If the new character c = s[r] is not in the set, the window simply grows. If it is, some earlier copy of c sits inside the window, and any valid window ending at r must start after that copy. So we remove characters from the left, one by one, until c is no longer in the set; then add c.

Why is it safe to never move l backwards? If s[l..r] contains a duplicate, then every window s[l'..r'] with l' ≤ l and r' ≥ r contains the same duplicate. So once a start has been ruled out for some end, it stays ruled out for every later end. This monotonic property is what makes any two-pointer window correct.

Algorithm.

  1. l = 0, empty set window, best = 0.
  2. For each r: while window contains s[r], remove s[l] and increment l.
  3. Add s[r], update best with r - l + 1.
static int better(String s) {
    Set<Character> window = new HashSet<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        while (window.contains(c)) {               // drop characters until the old copy of c is gone
            window.remove(s.charAt(l));
            l++;
        }
        window.add(c);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Complexity. Time O(2n) = O(n): each character is added to the set once (when r passes it) and removed at most once (when l passes it). Space O(min(n, 256)) for the set.

The inner while loop looks like it could make this quadratic, but the total number of iterations across the whole run is bounded by n, because l only moves forward and never passes r + 1.

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

Intuition. In Approach 2 we walk l forward one character at a time until we pass the previous copy of c. We can compute that destination directly: if we remember the most recent index last[c] where c appeared, the new left edge must be last[c] + 1. One subtlety decides correctness. The stored index might be older than the window, that is, last[c] < l. Then that copy of c is not in the window, there is no conflict, and l must not move. Jumping back to last[c] + 1 would re-admit characters we already threw out. So we jump only when last[c] >= l (equivalently, l = max(l, last[c] + 1)).

Algorithm.

  1. Fill last with -1. Set l = 0, best = 0.
  2. For each r with c = s[r]:
    • If last[c] >= l, set l = last[c] + 1.
    • Set last[c] = r.
    • Update best with r - l + 1.
  3. Return best.
static int optimal(String s) {
    int[] last = new int[256];
    Arrays.fill(last, -1);
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (last[c] >= l) l = last[c] + 1;        // previous copy is inside the window: jump past it
        last[c] = r;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Dry run on s = "abba", the classic trap:

r c last[c] before l after window best
0 a -1 0 “a” 1
1 b -1 0 “ab” 2
2 b 1 2 “b” 2
3 a 0 2 “ba” 2

At r = 3, last['a'] = 0 is left of l = 2. Without the >= l guard, l would jump back to 1 and report the window "bba" of length 3, which contains two bs.

Complexity. Time O(n): a single pass with constant work per character. Space O(1): a fixed 256-entry array. If the input could contain arbitrary Unicode characters, swap the array for a HashMap<Character, Integer>; the logic is identical.

Edge cases and pitfalls