Longest Substring Without Repeating Characters

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

문제 파악 [필수 작성]

문제이해

s 내에서 중복글자 없이 가장 길게 만들 수 있는 문자열

제한 조건 확인

무조건 O(n) 또는 O(nlogn) 으로 풀어라

아이디어

s끝까지 갈때까지
s에서 tmp_char 하나씩 받아옴
tmp_set에 tmp_char 존재하는지 확인
존재하지 않으면, tmp_char를 tmp_set과 tmp_q에 추가
존재하면, tmp_q 길이 max_len 에 업데이트 후
tmp_q가 남아있고, tmp_q.pop() 이 tmp_char랑 같을때까지
tmp_q.pop() tmp_set 도 적절히 remove

시간복잡도

O(n)

자료구조

max_len
tmp_q
tmp_set

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차 시도 (20분 소요)

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        tmp_set = set()
        tmp_q = deque([])
        max_len = 0

        for char in s:
            #print(tmp_q)
            if char not in tmp_set:
                tmp_q.append(char)
                tmp_set.add(char)
            else:
                max_len = max(max_len,len(tmp_q))
                while tmp_q:
                    poped = tmp_q.popleft()
                    tmp_set.remove(poped)
                    if char == poped:
                        tmp_q.append(char)
                        tmp_set.add(char)
                        break
            if tmp_q:
                max_len = max(max_len,len(tmp_q))
                
        return max_len

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.