리트코드_3 중복 문자 없는 가장 긴 부분 문자열_Medium (해시테이블_투포인터_슬라이딩 윈도우)

• 링크 : https://leetcode.com/problems/longest-substring-without-repeating-characters/

---

메모

• 중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 구해라

  • 문제 주의해야될 조건 : 기존 데이터의 인덱스가 그대로 유지되어야함
  • 3번 테케이서 wke 가 답 = 부분 문자열
  • 3번 테케에서 pwke는 답아님 = 서브시퀀스(subsequence)

• ex) abcabcbb

  • "abc"ab~~

• ex) pwwkew 이게핵심

  • pw"wke"~~

알고리즘 및 방법

• 나의 방식
  • for를 돌리면서 크게 3가지로 구분함
    • [i-1]과 [i]가 같은 경우
    • arr[i]가 정답 배열에 존재하는 경우 (중요) -->슬라이싱
    • 처음 등장하는 경우

ans = [arr[0]]                   첨에 하나 넣어주고
answer = 0

for i in (1~len)                 1부터 시작

    if arr[i-1] == arr[i]:       앞뒤 같은거면
        ans.clear()              기존에 있떤거 다 날려버려
        ans.append(arr[i])       대신 현재는 추가

    elif arr[i] in ans:          현재가 기존에 있는 값이야
        ans = ans[:i] + arr[i]   (중요)배열에 그 값 전까지 다 날려버리고 새로운거랑 ++ 

    else:                        완전 새로운거야
        ans.append(arr[i])       그냥 추가
        
    answer = max(answer, len(ans)) max길이를 기록하면 끗

책 해설

슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서
윈도우 내에 모든 문자가 중복이 없도록 투 포인터로 윈도우 사이즈를 조절하면서 풀이 라는데 뭔소린지 모르겠고
코드보면 이해됨
-> 그려보면 대충 감 옴

• 투포인터로 문제를 풀되, 둘 다 왼쪽에서 출발한다
• 해시테이블[key] = index 를 for문 마지막에 추가해주고
• for i in ~~안에서 (~> i가 포인터2)
  • if arr[i]가 또 등장했어 and pointer1가 ans[arr[i]]보다 왼쪽이야
    • pointer1의 위치를 ans[arr[i]]+1로 땡겨줌(오른쪽으로)
  • 아니야
    • max값 계산해 (= max(기존 맥스값, (i - pointer1위치) + 1)

---

히든테케 주의사항

진짜 너무 억지 아니냐

• 1번 : ""
  • 정답 0
• 2번 : " "
  • 정답 1

---

솔루션 코드 - 내가 푼

class Solution:
    def lengthOfLongestSubstring(self, arr: str) -> int:
        
        if arr == "":       return 0  # 1번 해결용
        elif len(arr) == 1: return 1  # 2번 해결용
        
        arr = list(arr)               # 만약을 대비한 공백도 인식
        
        ans = [arr[0]]
        answer = 0
        for i in range(1,len(arr)):
            if arr[i-1] == arr[i]:
                ans.clear()
                ans.append(arr[i])
            elif arr[i] in ans:
                ans = ans[ans.index(arr[i])+1:] + list(arr[i])
            else:
                ans.append(arr[i])
                
            answer = max(answer, len(ans))
        
        return answer

• 내가 짠 코드 테케 작동 과정
  • 순서는 다음과 같음
    • 정답값(= max(answer, len(ans))
    • 작동과정 프로세스

2
['a', 'b']
3
['a', 'b', 'c']
3
['b', 'c', 'a']
3
['c', 'a', 'b']
3
['a', 'b', 'c']
3
['c', 'b']
3
['b']
-------------------------------------------
1
['b']
1
['b']
1
['b']
1
['b']
-------------------------------------------
2
['p', 'w']
2
['w']
2
['w', 'k']
3
['w', 'k', 'e']
3
['k', 'e', 'w']
-------------------------------------------

---

솔루션 코드 - 책

• 나랑 생각한 방식은 같은데 나는 리스트를 또 씀, 여기는 투포인터로 수학적 계산만 함

class Solution:
    def lengthOfLongestSubstring(self, arr: str) -> int:
        
        ans = {}
        answer = pointer1 = 0
        
        for i, key in enumerate(arr):
            # 이미 등장했던 문자라면 'pointer1'위치를 오른쪽으로 이동
            if key in ans and pointer1 <= ans[key]:
                pointer1 = ans[key] + 1
            # 아니면 최대 부분문자열 길이 갱신
            else:
                answer = max(answer, i-pointer1 + 1)
                
            # 현재 문자 위치를 해시테이블에 추가
            ans[key] = i
            
        return answer