leetcode 3. Longest Substring Without Repeating Characters 풀이

문제 : 문자열 s 가 주어질 때 반복되는 문자가 없는 가장 긴 substring의 길이를 반환하라.

문제에서 얘기하는 substring이 subsequence가 아닌 점. substring이 무엇인지에 대해서 알고 있어야 풀 수 있다.

Follow up : asdfas 에서 정답은 asdf 즉 4가 될 것이다. asdfs는 subsequence이기 때문에 답이 될 수 없다.

 

아이디어 : sliding window 즉 two pointer 문제의 일종이다. sliding window란 우리가 어떤 거리를 지나가면서 차를 타고 간다고 가정할 때, 유리창 너머로 보이는 공간만 보일 때와 같다고 이해하면 된다.

 

 

코드 :

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        q = deque()
        d = dict()
        ans = 1
        for st in s:
            if st == " ":
                st = 'space'
            if not st in d:
                d[st] = 1
                q.append(st)
            else:
                ans = max(ans, len(q))
                while q:
                    a = q.popleft()
                    d.pop(a)
                    if a == st:
                        break
                q.append(st)
                d[st] = 1
        ans = max(ans, len(q))
        return ans
            

 

학습 포인트 : sliding window에 대해서 공부할 수 있었다. 많은 문제에 응용되므로 반드시 익히고 가자. dictionary key 값으로 공백을 사용할 수 없다는 것을 다시 한번 새겼다.

 

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