Given string s of lowercase letters, find the longest substring that has no repeated characters.
A "substring" is a consecutive sequence in the original string.
Example:
Explanation: The longest string without a repeated character is "abc".
longestNoDupeLength('abccc')
# 3longestNoDupeLength('axbx')
# 3longestNoDupeLength('deriveit')
# 5To solve this problem, you can use a sliding window approach. You want to grow keep adding a new element to the window, like this:
You eventually get to a duplicate letter, like this:
You have to remove one of the "b"'s from this window, because it's a duplicate. The trick is to delete letters from the beginning of the the window until you remove the very first duplicate.
You won't miss out on any valid solutions when you do this, because you've already considered the largest possible substring that involves the first "b" in the previous window. This means you've considered every possible solution to the problem.
To solve the problem, you can keep growing the window from the right, and shrinking it from the left. Here's the logic for this:
i = 0 # left index
window = set()
for j in range(len(s)): # right index
while s[j] in window:
# shrink window
window.remove(s[i])
i += 1
# grow window
window.add(s[j])Here's how you code this up:
def longestNoDupeLength(s):
i = 0 # left index
window = set()
maxlen = 0
for j in range(len(s)): # next elt
while s[j] in window:
# shrink window
window.remove(s[i])
i += 1
# grow window
window.add(s[j])
maxlen = max(maxlen, len(window))
return maxlen
Time Complexity O(n). We do a single for-loop.
Space Complexity O(1). We have to store 26 letters, which is O(26) = O(1).