[Leetcode] Longest Substring Without Repeating Characters (python)

    python
    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if not s:
                return 0
            answer = 1
            max_num = len(set(s))
            n = len(list(s))

            for group_size in range(2,max_num+1):
                for start_idx in range(0,n-group_size+1):
                    if len(set(s[start_idx:start_idx+group_size])) == group_size:
                        answer = group_size
                        break

            return answer

그냥 brute force로 다 구했다. dynamic programming 형식으로 우선 group_size는 logN의 사이즈이고 길이 (N)에 대해 연산을 수행하므로 O(NlogN)으로 예상.

• 안의 연산이 무겁다면??
  • 안의 연산에서 string slicing → 길이만큼 걸리므로 logN
  • set 생성 → 길이만큼 logN
  • len 반환 → O(1)
  • int 비교 → O(1)
• 총 연산은 다시 계산하니 O(N * (logN)^3) 이다.

결과
Runtime: 348 ms, faster than 18.41% of Python3 online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Longest Substring Without Repeating Characters.

solution을 참조해보니 O(n)으로 할 수 있는 방법이 있다!

dict를 이용하는 것.

• 원리는 문자열의 index를 루프를 돌며 dict로 실시간 갱신해나간다. 그리고 substring의 시작 index를 정의하고, 현재 index에서 시작 index를 빼서 길이를 구한다. 그렇게 저장한 길이를 이전값과 비교 후 최대값 길이를 저장해나간다. left_side는 이전 substring의 마지막 idx이다.
• 가령, “abbcda” 에서
• 처음 substring의 시작 index는 a보다 한칸 앞선 index를 -1이라 하면 -1이된다.
• 그리고 idx_dict = {“a”:0}으로 저장해준다. 다음 a가 나오면 이 idx를 살펴 새로운 substring 시작 위치를 지정해준다. 현재 길이는 -1과 0사이 이므로 1이다.
• 다음 “b”가 idx_dict에 없으므로 idx_dict = {“a”:0,”b”:1} 가 되고 left_side는 그대로이므로 현재 길이는 1-(-1)로 2가 된다.
• 다음 “b”는 idx_dict에 존재하므로 left_side를 기존 “b” idx (1)로 지정해준다. (이전 substring의 끝 idx)새로운 substring의 길이는 2 - 1 = 1이나, 이전 substring의 길이가 2이므로 최댓값은 2로 저장된다.
• 다음 “c”에서 “bc"의 길이 2가 저장되고
• 다음 “d”에서 “bcd”의 길이 3이 최댓값으로 저장
• 다음 “a"에서 기존 idx_dict에 “a”가 존재하나 기존 “a”의 idx는 현재 left_side보다 작으므로 substring의 시작점은 그대로 유지된다. 따라서 길이는 “bcda”의 길이인 4가 된다.

    python
    class Solution:
        def lengthOfLongestSubstring(self,s: 'str') -> 'int':
            idx_dict = {}
            max_len = 0
            left_side = -1
            for idx,ch in enumerate(s):
                if ch in idx_dict:
                    left_side = max(left_side,idx_dict[ch])
                current_len = idx - left_side
                max_len = max(current_len,max_len)
                idx_dict[ch] = idx
            return max_len

교훈

• 도저히 생각이 안나서 해답을 보긴 했다. dict를 for루프안에서 실시간으로 할당하는 게 아직 익숙하지 않다.
• 문제의 핵심은 가능한 substring을 저장하는 것이고, substring을 정의하는 것은 시작점, 끝점을 아는 것이다. 매번 새로운 시작점을 정의할 때는 같은 문자를 가진 값의 index를 찾고, 두 문자가 곂치지 않는 최대한 긴 시작점을 찾는다. 여기서 “같은”이란 단어가 중요하다. key의 고유성을 이용하면 dict[“a”]로 이전 index값을 손쉽게 구할 수 있다. 따라서 ‘dict를 이용하면 문제가 쉽게 풀리겠구나’란 생각이 들어야 한다.
• ex) abcddefga
  • a가 처음과 끝에 나왔다고 substring의 시작점, 끝점이 되지않는다.
  • 중간에 dd에 의해 새로운 시작점이 정의되었으므로, 그 것보다 이전의 index는 시작점이 될 수 없다.