[LeetCode 해석 및 풀이] 3.Longest Substring Without Repeating Characters

LeetCode 문제 해석 및 풀이 방법

 

문제 3.Longest Substring Without Repeating Characters(반복되는 글자 없는 가장 긴 부분 문자열)

바로가기

 

문제 설명

영문

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

한글

문자열 s가 주어졌을 때, 반복되는 글자가 없는 가장 긴 부문 문자열의 길이를 구하시오

 

제한조건

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

 

입출력 예

입력	출력
"abcabcbb"	3
"bbbbb"	1
"pwwkew"	3

 

 

해답 및 해설

파이썬 (Python)

neetcode 로드맵에 나온 대로 슬라이딩 윈도우를 이용하면 된다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l, r = 0, 0
        char_idx = {}
        max_len, cur_len = 0, 0
        
        while r < len(s):
            if s[r] in char_idx and char_idx[s[r]] >= l:
                l = char_idx[s[r]] + 1
                cur_len = r-l+1
            else:
                cur_len += 1
                if cur_len > max_len: 
                    max_len = cur_len
            char_idx[s[r]] = r
            r += 1
        
        return max_len

위는 dictionary을 이용한 직접 푼 풀이

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        l, r = 0, 0
        chars = set()
        
        while r < len(s):
            if s[r] not in chars:
                chars.add(s[r])
            else:
                max_len = max(max_len, r - l)
                while s[l] != s[r]:
                    seen.remove(s[l])
                    l += 1
                l += 1
            r += 1
            
        max_len = max(max_len, r - l)
        
        return max_len

set을 이용한 다른 사람의 풀이