MediumBlind75StringSliding Window

Longest Substring Without Repeating Characters

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

Examples

Input
s = 'abcabcbb'
Output
3

The answer is 'abc', with the length of 3.

Input
s = 'bbbbb'
Output
1

The answer is 'b', with the length of 1.

Input
s = 'pwwkew'
Output
3

The answer is 'wke', with the length of 3.

Constraints

  • •0 <= s.length <= 5 * 10^4
  • •s consists of English letters, digits, symbols and spaces.

Approaches

Generate all substrings and check if they contain repeating characters.

CodeT: O(n^3) | S: O(min(n, m))
def length_of_longest_substring(s):
    def has_no_repeats(sub):
        return len(sub) == len(set(sub))
    max_len = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            if has_no_repeats(s[i:j]):
                max_len = max(max_len, j - i)
    return max_len

Use a sliding window with a set to track characters.

CodeT: O(n) | S: O(min(n, m))
def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Use a hash map to store the last index of each character, allowing direct jumps.

Diagram

s = 'abcabcbb' right=0: 'a'->0, len=1 right=1: 'b'->1, len=2 right=2: 'c'->2, len=3 right=3: 'a' at 0>=left, left=1, 'a'->3, len=3 ...max_len stays 3
CodeT: O(n) | S: O(min(n, m))
def length_of_longest_substring(s):
    char_index = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)
    return max_len

Complexity Comparison

Brute Force
T: O(n^3)S: O(min(n, m))

Generate all substrings and check if they contain repeating characters.

Sliding Window with Set
T: O(n)S: O(min(n, m))

Use a sliding window with a set to track characters.

Sliding Window with HashMap
T: O(n)S: O(min(n, m))

Use a hash map to store the last index of each character, allowing direct jumps.

Common Mistakes

Using a fixed-size array instead of a hash map for character tracking

Not updating the left pointer correctly when a duplicate is found

Confusing substring (contiguous) with subsequence (non-contiguous)

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems