[leetcode] 3. Longest Substring Without Repeating Characters 파이썬 코드

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

 

character가 반복되지 않는 가장 긴 substring의 길이를 구하는 문제다.

 

left pointer와 right pointer를 이용했다. 

처음에는 lp와 rp가 당연히 0 index를 가리키고 있다.

이제 string s의 character를 하나씩 훑고 지나갈 것이다. 

 

s = "tmmzuxt"라는 string이 있다고 하자.

rp 가 처음에 0이므로 s[rp] = "t"이다. 

character를 담는 딕셔너리를 만들어줬다. 딕셔너리의 key는 character이고, value는 right pointer의 index다.

딕셔너리에 우선 character가 있는지 확인하고 없으면 딕셔너리에 추가해준다. 

"t"는 없으므로 딕셔너리에 추가될 것이다.

딕셔너리에 추가한 다음에 해야할 일은 길이를 구하는 일이다. 

lp와 rp를 빼고 1을 더해준 만큼의 길이가 지금까지 substring의 최대 길이다.

마지막으로 해야 하는 일은 rp를 오른쪽에 1칸 옮겨준다.

 

rp = 1일 때 s[rp] = "m"이다. 

이것도 딕셔너리에 없으므로 위와 같은 로직이다. 

 

자 그런데 이제 rp=2일 때 s[rp]="m"이다. 

어? 드디어 딕셔너리에 이미 있는 character가 나왔다. 

중복된 character가 나왔으니까 left pointer를 옮겨줘야 한다. 

left pointer를 옮길 때는 그 중복된 character를 제외시키고 나서 새로운 substring을 만들어야 하니까 

lp = string_dict[s[rp]] + 1

 

이렇게 lp를 설정해야 한다. 

 

그리고 딕셔너리에 있는 그 캐릭터의 rp 인덱스도 업데이트 해준다.

substring의 길이도 업데이트 해주고, rp 도 1을 더해줘서 s의 그 다음 character를 본다.

 

지금까지 설명한 것을 코드로 짜면 다음과 같다.

 

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        lp, rp = 0, 0
        # print(lp, rp)
        string_dict = dict()
        result = 0
        while rp < len(s):

            if s[rp] in string_dict: # 어? 딕셔너리에 있네?
                lp = string_dict[s[rp]] + 1 # lp 이동
                string_dict[s[rp]] = rp # index 업데이트
                result = max(result, rp - lp)
                rp += 1

            else:
                string_dict[s[rp]] = rp # index를 저장하자
                rp += 1
                result = max(result, rp - lp)

        return result

 

그런데 위의 코드는 틀린 코드다. 

 

s = "aabaab!bb"

 

s가 다음과 같을 때 정답이 3이어야 하는데 내 코드를 돌렸을 때 4가 나온다. 

 

디버깅을 열심히 해서 내 코드의 오류를 찾아냈다. 

a와 b가 중간에 많이 겹쳐서 lp가 업데이트 되는 과정에서 문제가 있었다.

가장 긴 substring은 "ab!" 이것이라서 길이가 3인데 

lp가 중간에 작아져서 "aab!" 이렇게 substring 길이를 카운트하게 된다.

 

따라서 lp가 줄어들면 안 되기 때문에 

if string_dict[s[rp]] + 1 > lp:  # 그 값이 lp보다 크면 lp 이동 (크지 않으면 lp 그대로)
    lp = string_dict[s[rp]] + 1

 

이 코드를 넣어줘야 한다. 

 

아래가 최종 코드이다.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        lp, rp = 0, 0
        # print(lp, rp)
        string_dict = dict()
        result = 0
        while rp < len(s):

            if s[rp] in string_dict: # 어? 딕셔너리에 있네?
                if string_dict[s[rp]] + 1 > lp:  # 그 값이 lp보다 크면 lp 이동 (크지 않으면 lp 그대로)
                    lp = string_dict[s[rp]] + 1
                string_dict[s[rp]] = rp # index 업데이트
                result = max(result, rp - lp + 1)
                rp += 1

            else:
                string_dict[s[rp]] = rp # index를 저장하자
                result = max(result, rp - lp + 1)
                rp += 1
        
        return result