Longest Substring Without Repeating Characters
DESCRIPTION (credit 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.
EXAMPLES
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.
Run your code to see results here
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):seen = {}max_length = 0start = 0for end in range(len(s)):seen[s[end]] = seen.get(s[end], 0) + 1while seen[s[end]] > 1:seen[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
Initializing Variables
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.
def longestSubstringWithoutRepeat(s):seen = {}max_length = 0start = 0for end in range(len(s)):seen[s[end]] = seen.get(s[end], 0) + 1while seen[s[end]] > 1:seen[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
Expanding window until duplicate g
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 b left in the window.
def longestSubstringWithoutRepeat(s):seen = {}max_length = 0start = 0for end in range(len(s)):seen[s[end]] = seen.get(s[end], 0) + 1while seen[s[end]] > 1:seen[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
Contracting window until duplicate g is removed
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.
def longestSubstringWithoutRepeat(s):seen = {}max_length = 0start = 0for end in range(len(s)):seen[s[end]] = seen.get(s[end], 0) + 1while seen[s[end]] > 1:seen[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
Expanding window until end of string
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 the index of the last appearance of s[end] + 1. 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 = 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
def longestSubstringWithoutRepeat(s):seen = {}max_length = 0start = 0for end in range(len(s)):seen[s[end]] = seen.get(s[end], 0) + 1while seen[s[end]] > 1:seen[s[start]] -= 1start += 1max_length = max(max_length, end - start + 1)return max_length
Loading comments...