37. Longest Substring Without Repeating Characters

1. 문제

Given a string sfind the length of the longest substring without repeating characters.

2. 답안

1. set

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

2. 사전

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        left = 0
        ans = 0
        
        for right in range(len(s)):
            if s(right) in dic:
                left = max(left, dic(s(right)) + 1)
            dic(s(right)) = right
            ans = max(ans, right - left + 1)
        
        return ans

중복하지 않는다는 점에서 주목해 set를 사용한다.

그 이외는 set나 dictionary 와도 알고리즘이 같다.

Exmaple 1을 예로 들자: “abcabcbb”

1) 출발점(left), 도착점(right) 설정

2) 출발점을 고정한 채로 right를 차례로 이동한다.

중복이 없으면 계속 추가합니다.

a → ab → abc

3) 중복 문자가 나오면 이전 문자를 삭제합니다.

abca→bca | bcab → cab | cabc → abc

4) 건너뛰고 같은 문자가 나오면 처음부터 삭제한다: abcb → cb

– 연속적인 부분 문자열을 요구하는 것이기 때문이다.

b만 제거하고 acb로 만들 수 없습니다.

5) 끝까지 계속: cbb → b

– 연속적인 부분 문자열을 요구하는 것이기 때문이다.

b만 제거하고 cb로 만들 수 없습니다.

6) 가장 긴 부분 문자열은 abc일 때, 길이는 3이다.

따라서 대답은 3입니다.

출처: set

출처: 사전

---

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters – LeetCode

Can you solve this real interview question? 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 “

leetcode.com