Longest Substring Without Repeating Characters

substring 관련한 문제는 brute force로 풀면 (i, j) 구간 (O(n^2))에 다시 각 문제별로 조건을 검사하는 비용이 곱해지게 되는데 (보통 input string의 글자 수에 비례), 여기서 빠르게 돌리고 싶을 때는 실행되는 (i, j)의 개수를 줄이는 수 밖에 없다. substring을 찾는 문제에서 부분 일치 테이블을 만들어놓으면 기존에 찾아놓은 substring 정보를 활용할 수 있듯이 이 문제에서도 앞에서 쓰던 정보를 그대로 활용할 수 있다.

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = 0
        d = {}
        start = 0
        
        for end in range(0, len(s)):
            c = s[end]
            if d.get(c) is None or d.get(c) < start:
                d[c] = end
                longest = max(longest, end-start +1)
            else: # d.get(c) >= start
                start = d.get(c) + 1
                d[c] = end

        return longest

루프가 도는 내내 지켜져야 하는 것은 구간 [start, end] 사이에 repeating character가 하나도 존재하면 안된다는 것이다. 새로 만난 character가 딕트에 없거나, start 이전에 나타났었으면 [start, end] 구간이 길어지는 것이고 start, end 사이에 있었으면 start를 뒤로 미뤄서 새 구간을 만든다.