Longest Substring Without Repeating Characters

MEDIUM✓ CHIP-TIMEDLC #3 — FULL STATEMENT ↗

The drill: Hunt the longest stretch of a string in which no character appears twice. The answer is just a length — the fight is keeping the window legal without restarting from scratch at every collision.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string of characters arrives, and the task is to find the length of the longest contiguous stretch within it where no character shows up more than once.

Only the length is reported, not the substring itself, and there can be many different stretches that tie for that longest length — any one of them proves the answer correct.

Case matters, so an uppercase and lowercase version of the same letter count as different characters, and the string can include digits, symbols, or spaces alongside letters.

EX 01

s = "racecar"

→ 4

BEST RUN IS THE FRONT FOUR

EX 02

s = ""

→ 0

EMPTY STRING

EX 03

s = "aaaa"

→ 1

ONE LETTER OVER AND OVER

string length runs from zero up to around fifty thousand characters
input may mix letters, digits, symbols, and spaces
character comparisons are case-sensitive
only the longest length is reported, not the substring achieving it

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Restarting the scan after every collision throws away everything you learned. When a repeat shows up, how much of the current window is actually poisoned?

HINT 2 THE STRUCTURE

Only the prefix up to and including the earlier copy is dead — everything after it is still repeat-free. Two pointers can keep that part alive.

HINT 3 ONE STEP FROM THE ANSWER

Slide with a char→last-index map: when the incoming character was last seen inside the window, jump the left edge to just past that old copy. Length is right − left + 1, every step.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE LAST-SEEN LEAPPATTERN · SLIDING WINDOW + LAST SEENs = "abba"

LAST SEEN INDEX

— empty —

STEP 1

Right pointer starts at 0, left at 0 — the map remembers each character's last seen index.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-substring-without-repeating-characters.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}  # char -> most recent index
        best = 0
        left = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1     # leap past the stale copy
            last[ch] = right
            best = max(best, right - left + 1)
        return best

TIME O(N)SPACE O(MIN(N, Α))PYTHON · RACE PACE · 11 LN

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        best = 0
        n = len(s)
        for start in range(n):
            seen = set()
            for end in range(start, n):     # extend until the first repeat
                if s[end] in seen:
                    break
                seen.add(s[end])
            best = max(best, len(seen))
        return best

TIME O(N²)SPACE O(MIN(N, Α))PYTHON · TRAINING PACE · 12 LN

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>(); // char -> most recent index
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            Integer prev = last.get(ch);
            if (prev != null && prev >= left) {
                left = prev + 1; // leap past the stale copy
            }
            last.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

TIME O(N)SPACE O(MIN(N, Α))JAVA · RACE PACE · 16 LN

class Solution {
    public int lengthOfLongestSubstring(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; // extend until the first repeat
            }
            best = Math.max(best, seen.size());
        }
        return best;
    }
}

TIME O(N²)SPACE O(MIN(N, Α))JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED