Problem statement

Given a string s, find the length of the longest substring without duplicate characters.

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", length 3.

Example 2

Input: s = "bbbbb"
Output: 1

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: "pwke" is a subsequence, not a substring.

Constraints

• 0 <= s.length <= 40
• s consists of lowercase English letters.

Hints for Longest Substring Without Repeating Characters

1. Hint 1

   Slide a window [start, i]; a repeat inside the window forces start forward.

2. Hint 2

   Remember the last index of each character to jump start directly.

How to solve Longest Substring Without Repeating Characters

Slide a window that never contains a repeat. When the incoming character was already seen inside the current window, jump the left edge to just past that earlier occurrence — one hop rather than shrinking step by step.

Approach

1. Keep a table of the last index at which each character was seen, and a left edge l.
2. For each right edge r, look up the character's last index.
3. If that index is at or after l, the character is inside the window — set l to lastIndex + 1.
4. Record the character's new last index and update the best with r - l + 1.

Why it works

The window [l, r] is kept free of duplicates by construction, so its length is a valid candidate at every step, and for each right edge the window is as large as it can possibly be. Jumping l directly to lastIndex + 1 is safe because every position between the old l and there would still contain the duplicate, so none of them could yield a longer valid window. That makes the sweep strictly linear, with l never moving backwards.

Complexity

• Time — O(n)
• Space — O(1) — the table holds at most the alphabet

Pitfalls

• Only jump the left edge when the previous occurrence is inside the window (lastIndex >= l); a stale index from before l must be ignored, or the window shrinks wrongly.
• Never move l backwards.
• Record the character's index after adjusting l, not before.
• An empty string answers 0.

Reference solution

Python

def lengthOfLongestSubstring(s: str) -> int:
    last = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

Java

public static int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];
    Arrays.fill(last, -1);
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        int code = s.charAt(r);
        if (last[code] >= l) l = last[code] + 1;
        last[code] = r;
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

C++

int lengthOfLongestSubstring(string s) {
    vector<int> last(128, -1);
    int l = 0, best = 0;
    for (int r = 0; r < (int) s.size(); r++) {
        int code = (unsigned char) s[r];
        if (last[code] >= l) l = last[code] + 1;
        last[code] = r;
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

JavaScript

var lengthOfLongestSubstring = function(s) {
    const last = new Map();
    let start = 0, best = 0;
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (last.has(ch) && last.get(ch) >= start) start = last.get(ch) + 1;
        last.set(ch, i);
        best = Math.max(best, i - start + 1);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium