5  Longest Substring Without Repeating Characters

Rank 3 · Pattern: sliding window with last-seen positions · Target: \(O(n)\) time

5.1 Problem definition

Given a string s, return the length of its longest contiguous substring that contains no repeated characters.

5.2 Clarifying questions

  1. Should I return the substring itself, its indices, or only its length?
  2. What does “character” mean for the chosen language, especially for Unicode input?
  3. Can the string be empty or null?
  4. Is character comparison case-sensitive?

5.3 Sample answers

  1. Return only the length.
  2. Use the language’s natural character iteration: Java UTF-16 char values, Python Unicode code points, or Rust char values. State that choice before coding.
  3. The string is non-null; an empty string is allowed and has answer 0.
  4. Yes. For example, A and a are different characters.

5.4 Data structure: last-seen map

A map stores each character’s most recent index. It lets start jump directly past a duplicate rather than remove characters one at a time.

HashMap<Character,Integer> uses get and put; a missing get returns null. Iterating a String by index processes UTF-16 code units.

A dict maps each one-character str value to its last index. enumerate(text) yields Unicode code points and indices together.

HashMap<char,usize> maps each Unicode scalar value to its last character index. text.chars().enumerate() avoids invalid byte indexing.

5.5 Approach and invariant

A brute-force solution starts at each position and extends until a repeat, costing \(O(n^2)\) time. A moving left boundary avoids reconsidering valid prefixes.

Let [start, end] be the current window. When s[end] was last seen at j, move start to at least j + 1.

start = max(start, lastSeen[c] + 1)

Taking the maximum is essential: an occurrence before the current window must not move start backward.

For abba:

end char prior index start after window best
0 a — 0 a 1
1 b — 0 ab 2
2 b 1 2 b 2
3 a 0 2, not 1 ba 2

Invariant: after processing end, [start,end] contains no duplicate characters, and start never decreases.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Advance the end pointer"]
  B{"Has this character been seen?"}
  C["YES: move start to max(current start, prior index + 1)"]
  D["NO: keep the current start"]
  E["Update the last-seen index and best length"]

  A --> B
  B --> C
  B --> D
  C --> E
  D --> E

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E plain;

5.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class LongestSubstringSolution {
    static int longestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int start = 0;
        int best = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            Integer previousIndex = lastSeen.get(c);
            if (previousIndex != null) {
                start = Math.max(start, previousIndex + 1);
            }
            lastSeen.put(c, end);
            best = Math.max(best, end - start + 1);
        }
        return best;
    }

    @Test public void emptyString() {
        assertEquals(0, longestSubstring(""));
    }

    @Test public void singleCharacterHasLengthOne() {
        assertEquals(1, longestSubstring("a"));
    }

    @Test public void entireUniqueStringIsLongest() {
        assertEquals(4, longestSubstring("abcd"));
    }

    @Test public void repeatedCharacterKeepsWindowAtOne() {
        assertEquals(1, longestSubstring("bbbbb"));
    }

    @Test public void repeatedPattern() {
        assertEquals(3, longestSubstring("abcabcbb"));
    }

    @Test public void doesNotMoveWindowBackward() {
        assertEquals(2, longestSubstring("abba"));
    }

    @Test public void findsOverlappingCandidate() {
        assertEquals(3, longestSubstring("dvdf"));
    }

    @Test public void comparesCharactersCaseSensitively() {
        assertEquals(2, longestSubstring("aA"));
    }

    public static void main(String[] args) {
        JUnitCore.main("LongestSubstringSolution");
    }
}
import unittest


def longest_substring(text):
    last_seen = {}
    start = 0
    best = 0

    for end, character in enumerate(text):
        if character in last_seen:
            start = max(start, last_seen[character] + 1)
        last_seen[character] = end
        best = max(best, end - start + 1)

    return best


class LongestSubstringTests(unittest.TestCase):
    def test_empty_string(self):
        self.assertEqual(0, longest_substring(""))

    def test_entire_unique_string(self):
        self.assertEqual(4, longest_substring("abcd"))

    def test_repeated_character(self):
        self.assertEqual(1, longest_substring("bbbbb"))

    def test_repeated_pattern(self):
        self.assertEqual(3, longest_substring("abcabcbb"))

    def test_does_not_move_window_backward(self):
        self.assertEqual(2, longest_substring("abba"))

    def test_finds_overlapping_candidate(self):
        self.assertEqual(3, longest_substring("dvdf"))

    def test_compares_characters_case_sensitively(self):
        self.assertEqual(2, longest_substring("aA"))


if __name__ == "__main__":
    unittest.main()
use std::collections::HashMap;

pub fn longest_substring(text: &str) -> usize {
    let mut last_seen = HashMap::new();
    let mut start = 0;
    let mut best = 0;

    for (end, character) in text.chars().enumerate() {
        if let Some(&previous_index) = last_seen.get(&character) {
            start = start.max(previous_index + 1);
        }
        last_seen.insert(character, end);
        best = best.max(end - start + 1);
    }

    best
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_string() {
        assert_eq!(0, longest_substring(""));
    }

    #[test]
    fn entire_unique_string() {
        assert_eq!(4, longest_substring("abcd"));
    }

    #[test]
    fn repeated_character() {
        assert_eq!(1, longest_substring("bbbbb"));
    }

    #[test]
    fn repeated_pattern() {
        assert_eq!(3, longest_substring("abcabcbb"));
    }

    #[test]
    fn does_not_move_window_backward() {
        assert_eq!(2, longest_substring("abba"));
    }

    #[test]
    fn counts_unicode_characters() {
        assert_eq!(3, longest_substring("aé🙂a"));
    }
}

5.7 High-value tests

Input Expected Purpose
"" 0 empty
"a" 1 one character
"bbbbb" 1 all repeated
"abcabcbb" 3 repeated pattern
"abba" 2 stale last-seen index
"dvdf" 3 overlapping candidates

5.8 Complexity and correctness

Every index is visited once and each map operation is expected \(O(1)\), giving expected \(O(n)\) time and \(O(u)\) space for \(u\) distinct characters.

If the new character repeats inside the window, moving start past its previous occurrence restores uniqueness. If its previous occurrence is outside the window, max keeps the already-valid boundary. Since every valid window ending at end can start no earlier, the maintained window is the longest valid one ending there; the maximum over all ends is the answer.

5.9 If the interviewer pushes

  • Return the substring by remembering the best start as well as its length.
  • For known ASCII input, replace the map with an initialized int[128] for smaller constants.
  • If the interviewer requires grapheme clusters as users perceive them, the standard libraries alone are not enough for all Unicode text; clarify whether code units or scalar values are acceptable.
  • A HashSet window is also \(O(n)\) and sometimes easier to derive, but moves the left edge one character at a time.

5.10 TDD interview script

Restate the contract: return a length, name the language’s character-iteration semantics, accept the empty string, compare case-sensitively, and assume a valid non-null string input. Then write this test list:

  1. Empty string
  2. One character
  3. All unique characters
  4. Immediate repeats
  5. Repeated pattern
  6. Stale previous occurrence
  7. Overlapping candidate

Drive one behavior at a time. Confirm red for the intended reason, implement the smallest general rule, rerun the complete class, and refactor only when green. Keep each test focused; for example, single-character and all-repeated behavior have separate names even though both return 1. Test returned lengths rather than the map or pointer positions.

From book/src, run:

./java/run.sh LongestSubstringSolution
./python/run.sh longest_substring_solution
./rust/run.sh longest_substring_solution

When abba is introduced, explain the defect it targets: an old occurrence of a lies before the current window, so assigning start = previous + 1 would move the left boundary backward. The test drives the monotonic max update.

5.10.1 Pseudocode

lastSeen = empty map
start = 0
best = 0

for end from 0 through s.length - 1:
    c = s[end]
    if c has a previous index:
        start = max(start, lastSeen[c] + 1)
    lastSeen[c] = end
    best = max(best, end - start + 1)

return best

The invariant is: after processing end, the window from start through end contains no repeated character, and start never moves backward.

5.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty window emptyString Introduce best = 0 and return it when the loop has no iterations.
2. First character singleCharacterHasLengthOne Scan by end and calculate the inclusive window length as end - start + 1.
3. Growing window entireUniqueStringIsLongest Update best on every iteration so a duplicate-free string grows to its full length.
4. Immediate duplicate repeatedCharacterKeepsWindowAtOne Store last-seen indices and move start just after the previous occurrence.
5. Repeated pattern repeatedPattern Exercise several grow-and-jump transitions while retaining the maximum length found earlier.
6. Monotonic boundary backward-window regression Change the boundary update to max(start, previousIndex + 1).
7. Overlapping candidate findsOverlappingCandidate Verify that a new candidate may begin inside the previous window and later become the best.
8. Case contract case-sensitive characters Confirm ordinary character-key equality; no normalization is added.

This build-out combines simple examples, boundary cases, and a targeted regression for the classic backward-window bug without coupling tests to a particular map implementation.