ToolMight LogoToolMight
MediumSliding WindowTwo PointersArrays & HashingPattern: Dynamic Sliding WindowPattern: Character Last-Seen Index Map

Longest Substring Without Repeating Characters

Find the length of the longest substring containing no duplicate characters. The quintessential problem for mastering dynamic variable-size sliding windows.

Problem Statement

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

Examples & Constraints

Example 1
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints
  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.

Sliding Window with Last-Seen Index Map

Optimal Approach
Time:O(n)
Space:O(min(n, m))

Expand the right window pointer while storing each character's latest index. When a duplicate appears, jump the left pointer forward past the previous occurrence in O(1) time.

Time ComplexityO(n)

The right pointer makes a single pass across the string of length N. The left pointer only jumps forward. Total work is linear O(n).

Space ComplexityO(min(n, m))

Consumes memory proportional to the character set size M (e.g. 128 for standard ASCII or 256 for extended ASCII).

Underlying algorithmic logic

The Core Mental Model: An Elastic Expanding Window

A naive brute force checks every possible substring of length 1 to N, taking O(n³) time to check uniqueness.

Instead, we maintain an elastic sliding window [left, right] that represents the current valid substring without duplicates:

  1. Maintain a hash map (or fixed array of 128/256 ASCII entries) storing the most recent index where each character was seen.
  2. Maintain left = 0 and maxLength = 0.
  3. Expand right from 0 to n - 1:
  • If s[right] was previously seen at prevIndex >= left, we have a duplicate inside our current active window!
  • Jump left = prevIndex + 1 (skipping the duplicate immediately without moving left one step at a time).
  • Update the character's last-seen index in our map: map[s[right]] = right.
  • Update our best window size: maxLength = max(maxLength, right - left + 1).
  1. Return maxLength.

Invariant: Window Never Contracts Backwards

Notice the check prevIndex >= left. If a character was seen at index 2, but our left pointer is already at index 5, that previous occurrence is outside the current window and can be safely ignored. This ensures left only moves forward.

Step-by-step execution walkthrough

1
Window [0..0] ('a')

Expand right to 0 ('a'). 'a' not seen. window: 'a', max = 1.

left = 0, right = 0 ('a'), map = {'a': 0}, max = 1
2
Window [0..1] ('ab')

Expand right to 1 ('b'). 'b' not seen. window: 'ab', max = 2.

left = 0, right = 1 ('b'), map = {'a': 0, 'b': 1}, max = 2
3
Window [0..2] ('abc')

Expand right to 2 ('c'). 'c' not seen. window: 'abc', max = 3.

left = 0, right = 2 ('c'), map = {'a': 0, 'b': 1, 'c': 2}, max = 3
4
Duplicate Encounter ('a')

Expand right to 3 ('a'). 'a' was seen at index 0 >= left (0). Jump left to 0 + 1 = 1.

left = 1, right = 3 ('a'), new window: 'bca', max = 3
Advantages
  • •Optimal O(n) single pass runtime
  • •Left pointer jumps directly without one-by-one decrements
Trade-offs
  • •Requires character set index array or hash map memory

Code Implementations

Copy & paste production-ready solutions for Sliding Window with Last-Seen Index Map in your language of choice

File: solution.py
Python
def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    max_len = 0
    left = 0
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len
if __name__ == "__main__":
    test1 = "abcabcbb"
    test2 = "pwwkew"
    print("test1 length:", length_of_longest_substring(test1))
    print("test2 length:", length_of_longest_substring(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyTwo Pointers
Visualizer

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic