greentea31's Note

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

풀이 과정

문자열을 입력받고 반복되는 문자가 없는 가장 긴 부분 문자열을 구하는 문제이다.

2중 for문으로 문자열을 읽으면서 문자를 딕셔너리에 넣고, 새로운 문자가 이전에 나왔는지 확인하면서 길이 변수를 1씩 늘려가는 방법으로도 풀이가 가능하다. O(N^2)으로 풀이가 되기는 하는데 풀고 나면 수행 시간 순위가 바닥임을 확인할 수 있다.

투 포인터로 O(N)에 해결이 가능하다.

문자열을 읽으면서 각 문자가 마지막으로 나온 위치를 used 딕셔너리 (26칸의 크기로 가진 배열로 처리해도 된다.)에 저장하고, 문자가 이전에 출현한 적이 있고, 투포인터의 시작 지점이 문자의 이전 출현 점보다 같거나 이전이면 같은 문자가 2번 이상 나온 것이므로 시작 지점을 1 늘려주고, 아니면 길이와 투포인터의 끝 지점을 갱신하는 방법으로 문제를 해결할 수 있다.

아래 제출 코드는 2중 반복문이고, 위 제출 코드는 투 포인터이다. 실행시간 차이가 20배 넘게 난다. 2중 반복문으로는 해결이 되긴 하지만 비효율적인 풀이이니 투 포인터를 이용해야 한다.

소스 코드

2중 반복문

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        for i in range(len(s)):
            length = 0
            dic = collections.defaultdict(int)
            for j in range(i, len(s)):
                if dic[s[j]] == 1:
                    break
                dic[s[j]] = 1
                length += 1
                answer = max(length, answer)
        return answer

투 포인터

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_len = max(max_len, index - start + 1)
            used[char] = index
        return max_len