3. Longest Substring Without Repeating Characters

See description at 3. Longest Substring Without Repeating Characters

Solution

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.

This is kind of a combination of the two solutions in the Two Sum problem.

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
        

Test Cases

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