[LeetCode] 3. Longest Substring Without Repeating Characters | LIM

문제

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

Longest Substring Without Repeating Characters - LeetCode

 

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

 

Example1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

 

Example2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

 

Example3

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

설명

주어진 문자 내에서 반복되지 않는 substring 문자의 최대 길이를 구하면 된다.

 

푼 방식( Two Pointer )

1. 처음 인덱스와 그다음 인덱스 설정 (i=0, j=1)

2. j 를 한 칸씩 이동하면서 저장된 문자와 같은 문자가 있을 경우 그전까지의 길이와 이전 max_len 비교

3-1. 만약 이전 max_len 보다 크다면 max_len 갱신 후 포인터 이동

3-2. 이전 max_len 보다 작을 경우 포인터만 이동

-> 포인터를 이동할 때 i는 기존에 있던 칸에서 한칸 오른쪽으로 이동, j의 경우 i 다음칸으로 이동

 

그림으로 보면 이러하다.

 

코드

from collections import defaultdict


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        sub = defaultdict(int)
        i, j = 0, 1
        max_len = 0
        if not len(s):
            return 0
        sub[s[0]] = 1
        while j < len(s):
            if not sub[s[j]]:
                sub[s[j]] = 1
            else:
                if len(''.join(list(sub.keys()))) > max_len:
                    max_len = len(''.join(list(sub.keys())))
                i += 1
                j = i
                sub = defaultdict(int)
                sub[s[i]] = 1
            j += 1
        return max(max_len, len(''.join(list(sub.keys()))))

 

결과

답은 맞았지만 결과가 좀 처참했다. 다른 방법으로 풀어보자

 

 

다른 풀이

1. 오른쪽 포인터가 한 칸씩 이동

2-1. 먄약 이미 dictionary에 값이 있고, 왼쪽 포인터가 오른쪽 포인터 키 값보다 작다면 왼쪽 포인터를 해당 키 값에서 한 칸 옮김

2-2. 값이 없다면 오른쪽 포인터와 왼쪽 포인터의 값을 뺀 다음 1을 더해서 max_len을 갱신함

3. 오른쪽 포인터의 값을 현재 인덱스로 업데이트

4. 문자열을 다 돈 후 max_len 을 return 함

 

 

코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        dic = {}
        left, right = 0, 0
        for right, val in enumerate(s):
            if val in dic and left <= dic[val]:
                left = dic[val] + 1
            else:
                ans = max(ans, right- left + 1)
            dic[val] = right
        return ans

 

결과

이전 코드보다 훨씬 개선되었다. 첫 번째 내가 푼 방식은 오른쪽 포인터를 다시 왼쪽으로 옮겨와서 진행하는 구조여서 반복이 많이 됐었던 반면 이렇게 풀게 되면 오른쪽 포인터가 중복으로 체크하는 일이 사라지게 된다.