3. Longest Substring Without Repeating Characters

Description

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

Example 1:

• Input: s = “abcabcbb”
• Output: 3
• Explanation: The answer is “abc”, with the length of 3.
  Note that “bca” and “cab” are also correct answers.

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 * 10⁴
• s consists of English letters, digits, symbols and spaces.

💡 Hint 1:
Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly.

Submitted Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_len = 0
        
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_len = max(max_len, (right - left + 1))
        
        return max_len

Runtime: 11 ms | Beats 78.99%
Memory: 19.09 MB | Beats 91.14%

seen에서 중복이 없다면 오른쪽 포인터를 이동시키고 중복이 나올 때는 왼쪽 포인터를 이동시키는 방법이다.

Other Solutions

1st

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        max_length = left = 0
        count = {}

        for right, c in enumerate(s):
            count[c] = 1 + count.get(c, 0)
            while count[c] > 1:
                count[s[left]] -= 1
                left += 1
        
            max_length = max(max_length, right - left + 1)

        return max_length

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)