[파이썬 알고리즘] 중복 문자 없는 가장 긴 부분 문자열

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

리트코드로 풀러 가기

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

입력: "abcabcbb"
출력: 3

입력: "bbbbb"
출력: 1

---

문자열의 길이로부터 차례대로 슬라이싱을 통해 잘라주게끔 문제를 풀 수도 있지만, 해시맵을 통한 풀이로 시간 복잡도를 O(n)으로 줄여보자.

슬라이딩 윈도우와 투 포인터

투 포인터를 이용한 슬라이딩 윈도우에서의 중복 문자가 없는지 검사하여 문제를 풀어보자.

포인터의 하나는 슬라이딩 윈도우의 첫 부분으로, 중복된 문자가 나오기 전까지 고정한다.

나머지 하나는, 인덱스 0부터 차례대로 순회하며 현재 슬라이딩 윈도우에 해당 인덱스의 문자가 존재하는지를 해시맵을 통해 살펴본다.

만약 존재하지 않는다면, 현재 슬라이딩 윈도우에 해당 인덱스의 문자를 포함시키고, 현재까지 검출된 부분 문자열의 길이와 max 연산을 통해 가장 긴 부분 문자열을(길이) 업데이트한다.

존재한다면, 해시맵에 저장되어 있는 해당 문자의 인덱스의 다음으로 첫 번째 포인터(슬라이딩 윈도우의 시작 부분)를 이동시킨다.

위의 연산을 끝낸 뒤, 해시맵에 저장된 해당 문자를 업데이트 시킨다.

hash[char] = index

이러한 이터레이션으로 문자열의 끝까지 진행되면 가장 긴 부분 문자열의 길이를 알 수 있다.

위의 과정을 코드로 옮기면 다음과 같다.

def lengthOfLongestSubstring(self, s):
    used = {}
    max_length = start = 0

    for i, char in enumerate(s):
        if (char in used) and (start <= used[char]):  # 1
            start = used[char] + 1
        else:
            max_length = max(max_length, i - start + 1)
        used[char] = i

    return max_length

# 1 부분에서 (start <= used[char]) 를 조건으로 묶어주는 이유는 슬라이딩 윈도우 안에서만 조건을 검출하기 위해서이다.