leetcode-3 - Longest Substring Without Repeating Characters

動機

複習sliding windows

Problem

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = abcabcbbOutput: 3Explanation: The answer is abc, with the length of 3.

Example 2:

Input: s = bbbbbOutput: 1Explanation: The answer is b, with the length of 1.

Example 3:

Input: s = pwwkewOutput: 3Explanation: 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.

Example 4:

Input: s = Output: 0

Constraints:

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

Sol

sliding windows用set去追蹤windows的內容物

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ss = set()
        a = 0; b = 0
        ans = 0
        while a < len(s) and b < len(s):
            if s[b] not in ss:
                ss.add(s[b])
                ans = max(ans,b-a+1)
                b+=1
            else:
                ss.remove(s[a])
                a+=1
        return ans