Sliding Window
Longest Substring Without Repeating Characters
medium
Count: 10
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.
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.
Visualization
def longestSubstringWithoutRepeat(s):state = {}max_length = 0start = 0for end in range(len(s)):state[s[end]] = state.get(s[end], 0) + 1while state[s[end]] > 1:state[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
start
longest substring without repeating characters
0 / 1
We use a for-loop to increment end to repeatedly expand the window. Each time we expand the window, we first increment the count of s[end] in state. As long as the character at end is not a duplicate character in the window, we can compare the length of the current window to the longest window we've seen so far, and continue expanding. The character at end is a duplicate if state[s[end]] > 1.
Visualization
def longestSubstringWithoutRepeat(s):state = {}max_length = 0start = 0for end in range(len(s)):state[s[end]] = state.get(s[end], 0) + 1while state[s[end]] > 1:state[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
start: 0 | end: -
initialize variables
0 / 7
At this point, we have to contract the window because it contains more than one g. We do this by removing the leftmost character (start += 1) from the window, and decrementing its count in state until there is only one g left in the window.
Visualization
def longestSubstringWithoutRepeat(s):state = {}max_length = 0start = 0for end in range(len(s)):state[s[end]] = state.get(s[end], 0) + 1while state[s[end]] > 1:state[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
start: 0 | end: 3
expand window
0 / 2
At this point, our window is valid again, and we can continue this process of expanding and contracting the window until end reaches the end of the string.
Visualization
def longestSubstringWithoutRepeat(s):state = {}max_length = 0start = 0for end in range(len(s)):state[s[end]] = state.get(s[end], 0) + 1while state[s[end]] > 1:state[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
start: 2 | end: 3
contract window
0 / 15
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.
Solution
def longestSubstringWithoutRepeat(s):state = {}start = 0max_length = 0for end in range(len(s)):if s[end] in state:start = max(start, state[s[end]] + 1)state[s[end]] = endmax_length = max(max_length, end - start + 1)return max_length
Solution
Visualization
Try these examples:
def longestSubstringWithoutRepeat(s):state = {}max_length = 0start = 0for end in range(len(s)):state[s[end]] = state.get(s[end], 0) + 1while state[s[end]] > 1:state[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
start
longest substring without repeating characters
0 / 25
Mark as read
Your account is free and you can post anonymously if you choose.