[LeetCode - 003] Longest Substring Without Repeating Characters

문제

문제링크

string이 하나 주어지면, 중복 문자가 없는 substring의 최장 길이를 구하시오.

Example 1:

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

풀이

가장 먼저 완전 탐색(Brute Force)를 떠올릴 수 있다.
하지만 이는 O(n^3)에 해당하므로 개선된 알고리즘을 찾아보는 것이 좋다.
특히나, LeetCode와 같이 범위가 제대로 주어지지 않는 경우는 유의해야한다.

이 경우에는 슬라이딩 윈도우방식으로 풀어야한다.
슬라이딩 윈도우는 정해진 창의 크기를 가지고 연속된 데이터를 살펴보는데 주로 활용된다.

참고로, 투포인터 알고리즘과 비슷하지만 이는 창의 크기가 변화하는 차이점을 가지고 있다.

아래서 사용하는 방법은 사전형 자료형을 활용해 이전 중복 알파벳과의 자리를 기억하는 방식으로 접근한다. O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dict_s = dict()
        start, answer = 0, 0
        for end in range(len(s)):
            if s[end] in dict_s:
                # 존재하는 경우
                start = max(dict_s[s[end]], start)

            dict_s[s[end]] = end + 1
            answer = max(answer, end-start+1)

        return answer

외에도, set에 저장을 하면서 최대 길이를 유지하는 방식도 가능하다 O(2n)

정리

연속되는 문자열 처리에서 투포인터와 슬라이딩 윈도우가 자주활용된다는 점을 기억하자!
Hash Table를 활용하면 쉽게 구현할 수 있다.