3. Longest Substring Without Repeating Characters
Given an input string like "abcabcbb" we need to find the longest substring without repeating characters.
Two pointers are used to keep track of the start and end (left and right) of a substring. A cache is also used to store the seen characters. The left and right pointers are initially set to the first index in the array. The character at the right pointer is stored in the cache. The key is the character and the value is the index position. When a duplicate character is seen, then the left pointer is moved.
def lengthOfLongestSubstring(self, s: str) -> int:
seen = defaultdict(int)
left, right = 0, 0
answer = 0
while right < len(s) :
if s[right] in seen:
# need to take the max here because the left pointer may have moved past
# the index where the letter was previously seen. case: "abba"
left = max(left, seen[s[right]] + 1)
answer = max(answer, right - left + 1)
seen[s[right]] = right
right += 1
return answer
input | output |
|---|---|
"abcabcbb" | 3 |
"bbbbb" | 1 |
"pwwkew" | 3 |
"ababab" | 2 |
"a" | 1 |
"ab" | 2 |
"abbc" | 2 |
"abbcbdefgh" | 7 |
"abbcbdefghc" | 7 |
" " | 1 |
"a b%7c7" | 6 |
"" | 0 |
"bb" | 1 |
"abba" | 2 |
"1212345" | 5 |
Last modified 1yr ago