Sliding Window

Longest Substring Without Repeating Characters

medium

DESCRIPTION (inspired by Leetcode.com)

Write a function to return the length of the longest substring in a provided string s where all characters in the substring are distinct.

Example 1: Input:

s = "eghghhgg"

Output:

3

The longest substring without repeating characters is "egh" with length of 3.

Example 2: Input:

s = "substring"

Output:

8

The answer is "ubstring" with length of 8.

💻 Desktop Required

The code editor works best on larger screens.

Explanation

This solution uses a variable-length sliding window to consider all substrings without repeating characters, and returns the length of the longest one at the end.

We represent the state of the current window with a dictionary state which maps each character to the number of times it appears in the window.

def longestSubstringWithoutRepeat(s):
  state = {}
  max_length = 0
  start = 0

for end in range(len(s)):
    state[s[end]] = state.get(s[end], 0) + 1
    while state[s[end]] > 1:
      state[s[start]] -= 1
      start += 1

max_length = max(max_length, end - start + 1)
  return max_length

Alternate (Faster) Solution

An slightly more optimized solution represents the state of each window with a dictionary mapping each character to the index at which it last appeared in the window.

Each time we increment end to expand the window, we first check if the character at end is a duplicate by checking if s[end] is in the dictionary. If it is, we can contract the window until it is valid again by setting start to max(start, last_index + 1) where last_index is the previous appearance of s[end]. We use max() to ensure start never moves backward (the previous occurrence might be before the current window). This is faster because we can contract the window in one operation instead of using a while-loop to do it incrementally.

def longestSubstringWithoutRepeat(s):
    state = {}
    start = 0
    max_length = 0

for end in range(len(s)):
        if s[end] in state:
            start = max(start, state[s[end]] + 1)

state[s[end]] = end
        max_length = max(max_length, end - start + 1)
    return max_length

Solution

def longestSubstringWithoutRepeat(s):
  state = {}
  max_length = 0
  start = 0

for end in range(len(s)):
    state[s[end]] = state.get(s[end], 0) + 1
    while state[s[end]] > 1:
      state[s[start]] -= 1
      start += 1

max_length = max(max_length, end - start + 1)
  return max_length