중복 문자 없는 가장 긴 부분 문자열

문제

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라 

 

· 입출력 예

string	return
"abcabcbb"	3 (abc)
"bbbbb"	1 (b)
"pwwkew"	3 (wke)

---

풀이

1. 슬라이딩 윈도우와 투 포인터 사이즈 조절

def lengthOfLongestSubstring(s: str) -> int:
    used = {}
    max_length = start = 0 
    for index, char in enumerate(s):
        if char in used and start <= used[char]:
            start = used[char] + 1 
        else:
            max_length = max(max_length, index - start + 1)
        
        used[char] = index 
    return max_length

투 포인터로 문제를 풀이하였는데, 포인터 2개 모두 왼쪽에서 출발한다. 두 번째 포인터 (index)를 오른쪽으로 확장시켜 나가며 문자열을 검사한다. 문자가 앞서 등장했는지 여부를 판단하고, 등장했을 경우 시작점을 갱신한다 (start = used[char] + 1). 등장했는지 여부를 판단할 때, 슬라이딩 윈도우 범위 밖의 문자는 비교 대상에 포함하면 안되기 때문에 start <= used[char] 조건을 추가해주었다.

 

등장하지 않았던, 처음 보는 문자라면 max 함수를 통해 부분 문자열의 길이를 확인하며 더 큰 값인 경우, 최대 길이를 갱신한다.