3. Longest Substring Without Repeating Characters

1. Description

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

2. Example

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.

3. Solution

• Runtime: 15ms
• Time Complexity: O(N)
• 설명
  • set()을 통해 현재 부분 문자열에서 사용된 문자들을 저장하는 set을 지정한다.
  • r은 오른쪽 포인터 역할을 하며, 문자열 s를 순회한다.
  • s[r]가 이미 charset에 존재하면, 중복을 없애기 위해 s[1]을 제거하고 l을 오른쪽으로 이동시킨다.
    • 현재 charset에 있는 문장려은 항상 중복이 없는 상태를 유지한다.
    • 📌while문을 통해 중복되지 않을 때까지 돌린다. 이를 통해 중복되지 않은 상태에서 길이를 잰다.
  • 중복되지 않은 s[r]을 charset에 추가한다.
  • res는 중복되지 않은 문자열의 최대 길이를 저장한다.
    • r-l+1과 비교하여 최대 길이를 구한다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0
 
        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

4. What I Learned

References

• ChatGPT