리트코드 3번 Longest Substring without Repeating Character

Problem

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

Solution

내 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start, end, max_len = 0, 0, 0
        substring = ""

        while end < len(s):
            if s[end] not in substring:
                substring += s[end]
                max_len = max(max_len, len(substring))
                end += 1

            else:
                substring = ""
                while end < len(s):
                    start += 1
                    end = start+max_len
                    substring = s[start:end]
					# 새로운 substring에 중복이 있다면 위 과정 반복
                    if len(set(substring)) != max_len:
                        continue
                    else:
                        break

        return max_len

슬라이딩 윈도우를 이용하여 풀이하였다.

현재 문자열의 처음과 끝의 idx를 각각 start, end로 표기하며 중복이 아니라면 end를 늘리며 탐색한다. 만약 중복인 단어가 나온다면 start를 다음 idx로 옮기고 현재 최대 길이만큼 새로운 substring을 할당한다. 새로운 substring에 중복되는 글자가 있다면 start를 다시 +1 을 하고 확인한다.

다른 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length, start = 0, 0

        for idx, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_length = max(max_length, idx - start + 1)

            used[char] = idx

        return max_length

dictionary를 이용하여 해당 글자의 마지막 위치를 기록한 풀이이다. 훨씬 깔끔하고 성능이 좋다.

Reference

파이썬 알고리즘 인터뷰 30번