leetcode 3

문제 내용

문자열의 substring 중, 중복이 없는 substring을 구하는데 제일 긴 경우의 길이를 찾는 문제입니다.

1번째 풀이 방식

-> 처음 투 포인터를 이용해서 문제를 푸려고 생각했습니다. substring이 중복인지 찾는 방식은 set을 사용했습니다. 중복이라고 판단되면 이전까지의 문자열의 길이들 중 제일 긴 문자열을 뽑는 방식을 선택했습니다. 이 과정이 굉장히 느리기 때문에 실제로 상위 90%의 속도를 내서 다른 방식을 찾다 2번째 풀이방식을 구현했습니다.

import collections 

def lengthOfLongestSubstring(s: str) -> int:
    max_cnt = 0 
    # max_string = ''
    p1 = 0
    p2 = 0
    while True:
        if p2 > len(s) -1:
            break  
            
        p2 +=1 
        if p2 - p1 != len(set(s[p1:p2])): # if duplicate exists
            p2 -=1 # Go back to previous substring's end index  
            if max_cnt < p2 - p1: # check the current max result 
                # max_string = s[p1:p2]
                max_cnt =  p2 - p1 
            # print(max_string, p2, p1)
            p1 +=1 
            p2 = p1
    if max_cnt < p2 - p1: # After while loop check the rest of the end substring
        # max_string = s[p1:p2]
        max_cnt =  p2 - p1 
    # print(max_string)
    return max_cnt 

# print(lengthOfLongestSubstring(" "))

2번째 풀이방식

이번에는 deque를 사용해서 queue 방식으로 풀었습니다. 실제로 문자열을 loop 돌면서, 만약 중복된 문자열이 들어오려고 하면, queue에 넣기 전에 현재 queue에 있는 substring 길이와 max_cnt를 비교하여 더 큰 값으로 갱신해줍니다.
그리고나서 현재 들어오려는 문자열이 pop될때까지 pop시키고, append해줍니다.
즉, queue 사용해서 현재 substring을 따로 뽑아내는 것이기에 두 개의 포인터를 사용하지 않고 구현했습니다.

import collections 
def lengthOfLongestSubstring(s: str) -> int:
    max_cnt = 0 
    queue = collections.deque()

    for i in range(len(s)):
        if s[i] in queue: # 중복된 문자열이 들어오려고 하면 
            max_cnt = max(max_cnt, len(queue))
            while True:
                if queue.popleft() == s[i]:
                    break
            queue.append(s[i])

        else:
            queue.append(s[i])
    max_cnt = max(max_cnt, len(queue))
    return(max_cnt)

print(lengthOfLongestSubstring("bbbbb")) #1