[LeetCode] 3. Longest Substring Without Repeating Characters

LeetCode 3번 Longest Substring Without Repeating Characters

string

 

---

 

문제

 

이 문제는 반복되는 알파벳이 나오지 않는 가장 큰 문자열을 반환하는 문제이다.

코테에서 보통 1번에 나오는 문자열관련 문제들과 유사했다.

 

 

과정

1) 처음에는 모든 경우를 구하기 위해서 2중 반복문을 사용했었다.

# case 986) Time Limit Exceeded Error!!

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        for i in range(len(s)):
            num = []
            cnt = 0
            for j in range(i,len(s)):
                if s[j] in num:
                    num = [s[j]]
                    cnt = 1
                else:
                    num.append(s[j])
                    cnt += 1
                answer = max(answer, cnt)
        return answer

 

아무래도 최악의 경우 10**4 * 10**4 = 1억에 해당하는 시간복잡도가 발생하므로 미흡한 코드였다.

986번의 testcase에서 Time Limit Exceeded 에러가 발생하면서 조금 더 효율적인 로직을 짜야 했다.

 

 

2) 두 번째로 짜게 된 코드는  deque를 사용했다.

deque를 사용해서 알파벳의 인덱스를 저장하고 반복되는 알파벳이 나오면 해당 인덱스까지 pop을 진행해줬다.

 

1. deque 선언
2.  s만큼 반복
   1. 해당 값이 q에 있을 경우
      1. 중복되는 알파벳의 인덱스를 찾기
      2. 해당 index까지 popleft()를 수행하여 삭제
      3. 현재 알파벳 값은 q에 넣어주기
   2. 해당 값이 q에 없을 경우
      1. 현재 알파벳 값을 q에 넣어주기
   3. answer값과 q의 길이를 비교하여 더 큰 값으로 answer 갱신
3. return answer

 

 

소스코드

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        q = deque()
        for idx, num in enumerate(s):
            if num in q:
                index = q.index(num)    # 큐 내에 num이 위치하는 index 리턴
                for i in range(index+1):    # 해당 알파벳의 index까지 pop진행
                    q.popleft()    
                q.append(num)
            else:
                q.append(num)
            answer = max(answer, len(q))
            # print(idx, q, answer)
        return answer

 

 

통과

 

---

 

 

// 2023-08-03 스터디 과제