3. Longest Substring Without Repeating Characters

가장 긴 부분 문자열 찾는 문제, 단 문자열 안에 중복이 없어야 한다. 

 

나는 for문 2번 돌려서 풀긴했는데, 만약 input의 길이가 증가하면 시간 초과 날것이다.

    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0

        for idx, ch in enumerate(s):
            cnt = 0
            c = ""
            for ch in s[idx:]:
                if ch in c:
                    break
                else:
                    c += ch
                    cnt += 1
            ans = max(ans, cnt)
        return ans

이전에 배운 hash를 여기서 사용하면 for문 한번과 hash 접근으로 가능하다. 

    def lengthOfLongestSubstring(self, s: str) -> int:
        max_length = start = 0
        used = {}
        for idx, ch in enumerate(s):
            # 이미 Dict에 있는경우 start값을 갱신해주자
            if ch in used and start <= used[ch]:
                start = used[ch]+1
            else:
                max_length = max(max_length, idx-start+1)

            used[ch] = idx
        return max_length

속도 차이가 300ms이상 나는 것을 볼 수 있다.