Leetcode 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest 

substring without repeating characters.

Example 1:Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.

Example 2:Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.

Example 3:Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

The key is awaring the edge case and the duplicated character can locate any postion before or after start index, so it’s needed to check if the position is greater than start index to avoid setting the start index back.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # check edge case
        if len(s) == 0:
            return 0

        ans = 0
        start = 0

        dup = {}

        for i, character in enumerate(s):
            position = dup.get(character)

            # check the postion is greater or equal to start before setting it back to start
            if position != None and position >= start:
                start = position + 1
            else:
                ans = max(ans, i - start + 1)

            dup[character] = i
        
        return ans