[LeetCode] Longest Substring Without Repeating Characters

Descirption

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

주어진 스트링에서 중복이 없는 가장 긴 서브 스트링의 길이를 찾는 문제다.

Code

현재 서브 스트링의 시작 인덱스, 끝 인덱스 두개의 포인터를 두고, 현재 서브 스트링의 마지막 인덱스의 문자값과 중복되면 시작 인덱스를, 중복되지 않으면 끝 인덱스를 증가 시키는 것으로 문제를 해결 할 수 있다.

중복체크는 딕셔너리의 키 존재 여부로 판단하여, O(1)이고 한번의 순회에 두개의 포인터 중 하나는 반드시 증가하기 때문에, 최악의 경우 2n 만큼 순회한다. 따라서 시간 복잡도는 O(2n)이다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0

        start_idx, end_idx = 0, 1
        ans = 0
        collector = {s[0]: True}

        is_end = start_idx == len(s) or end_idx >= len(s)

        while not is_end:
            """중복되면 start ++, 아니면 end를 ++"""
            cur_char = s[end_idx]

            if collector.get(cur_char):
                first_char = s[start_idx]
                collector.pop(first_char)
                ans = max(ans, end_idx - start_idx)
                start_idx += 1
            else:
                collector[cur_char] = True
                end_idx += 1

            is_end = start_idx == len(s) or end_idx >= len(s)

        return max(ans, end_idx - start_idx)