Leetcode 3

longest substring

substring 안에서 문자 겹치면 안됨

언어: python3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0   # start indicates left pointer
        max_len = 0
        used = {}
        for index, char in enumerate(s): # index indicates right pointer
            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

index: rightmost pointer
start: leftmost pointer

divide and conquer를 생각해보았지만 중간 영역에서 어차피 위의 과정을 거쳐야 하므로 iteration 한번으로 처리
time complexity : O(n)

출처: 파이썬 알고리즘 인터뷰