3. Longest Substring Without Repeating Characters

중복되지 않는 알파벳만을 포함하는 연속되는 문자열의 최대 길이를 구하는 문제이다.

 

예) abbcda -> 'bcda' => 4

     abba -> 'ab' or 'ba' => 2

 

처음에는 브루트포스를 생각했지만, 문자열의 길이가 길었고, O(n^2)은 너무 길었다.

예전에 비슷한 문제를 dp로 풀었던 것 같지만 도저히 모르겠고, 솔루션을 살짝 보고

" Dictionary와 left 와 right라는 인덱스를 가르키는 변수 "를 통해 문제를 해결하기로 했다.

---

1. right를 증가시켜주면서 구간을 늘려나간다.

 

2. 만약, 처음 나오는 알파벳이라면, 알파벳을 dictionary에 넣고, value에는 index를 넣어준다.

 

3. 만약, 딕셔너리에 존재하는 알파벳이라면, left를 그 전 같은 알파벳이 위치한 다음 index로 바꿔준다.(구간이 같은 알파벳을 갖지 못하게 해주는 역할)

 

** left값이 그 전 알파벳의 index + 1 보다 크다면 그대로 left값을 유지해야한다. (어차피 구간이 그 전 알파벳을 포함하지 않으므로) (밑 수기로 쓴 예제 중 파란 부분 참조)

 

 

* 딕셔너리에 key값이 존재하는지를 알려주는 것은 in 이다. <-> not in b = {'a':1} if 'a' in b: print('a는 딕셔너리 key값에 존재합니다.') if 1 in b.values(): print('1은 딕셔너리 value값에 존재합니다.')

파이썬 dict 딕셔너리 사전 사용법 정리 (keys, values, items) (withcoding.com)

파이썬 dict 딕셔너리 사전 사용법 정리 (keys, values, items)

소스 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0 #구간의 left index
        right = 0 #구간의 right index
        box = {} #구간에 존재하는 알파벳 : 가장 최근에 마주쳤을 때의 index
        maxi = 0 # 구간 길이 최댓값
        if len(s) == 0:
            return maxi
        while right != len(s):
            if s[right] not in box: #처음보는 알파벳일 경우
                box[s[right]] = right
            else: #알파벳 재출현의 경우
                if left < box[s[right]] + 1: #전의 알파벳 index가 left작으면 구간에 어차피 포함x -> left 그대로
                    left = box[s[right]] + 1
                box[s[right]] = right
            if (right - left + 1) > maxi:
                    maxi = right - left + 1
            right += 1
        return maxi

 

이런 '연속되는', '구간' 문제는 left,right 인덱스를 활용하는 문제가 많은 것 같으니 잘 기억해야겠다.