문자열 s와 숫자 k가 주어졌을 때, 서로 다른 문자가 최대 k개만 포함된 가장 긴 부분 문자열(substring)의 길이를 구하는 문제입니다.
예를 들어, k = 3이고 s = "kolkata"라고 가정해 보겠습니다. 이 경우 정답은 4입니다. 서로 다른 3개의 문자를 포함하는 가장 긴 부분 문자열이 "kolk"와 "kata" 두 개이며, 둘 다 길이가 4이기 때문입니다.
접근 방법: 슬라이딩 윈도우(Sliding Window)
이 문제는 슬라이딩 윈도우 기법과 해시 맵(딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 개의 포인터 left와 right로 윈도우 범위를 관리합니다.
- 딕셔너리(table)에는 현재 윈도우 내 각 문자의 등장 횟수를 저장합니다.
- 윈도우 내 고유한 문자의 개수가 k 이하이면 정답(ans)을 갱신합니다.
- 고유한 문자의 개수가 k를 초과하면, left 포인터를 오른쪽으로 이동시키며 해당 문자의 빈도를 줄여 윈도우를 축소합니다. 빈도가 0이 되면 딕셔너리에서 해당 문자를 제거합니다.
알고리즘 단계
- ans := 0, left := 0으로 초기화하고, 빈 딕셔너리 table을 생성합니다.
- right를 0부터 s의 길이 - 1까지 반복합니다.
- table[s[right]]의 값을 1 증가시킵니다.
- table의 크기(고유 문자 수)가 k 이하이면, ans와 (right - left + 1) 중 더 큰 값으로 ans를 갱신합니다.
- 그렇지 않으면, table의 크기가 k 이하가 될 때까지 다음을 반복합니다.
- left_char := s[left]
- table[left_char]의 값이 1이면 해당 키를 삭제하고, 그렇지 않으면 값을 1 감소시킵니다.
- left를 1 증가시킵니다.
- 반복이 끝나면 ans를 반환합니다.
구현 예제
class Solution:
def solve(self, k, s):
ans = 0
left = 0
table = {}
for right in range(len(s)):
table[s[right]] = table.get(s[right], 0) + 1
if len(table) <= k:
ans = max(ans, right - left + 1)
else:
while len(table) > k:
left_char = s[left]
if table[left_char] == 1:
table.pop(left_char)
else:
table[left_char] -= 1
left += 1
return ans
ob = Solution()
k = 3
s = "kolkata"
print(ob.solve(k, s))입력
k = 3, s = "kolkata"
출력
4
복잡도 분석
- 시간 복잡도: O(n) — left와 right 포인터가 각각 문자열을 한 번씩만 순회합니다.
- 공간 복잡도: O(k) — 딕셔너리에는 최대 k+1개의 고유 문자만 저장됩니다.
이처럼 슬라이딩 윈도우 기법을 사용하면 모든 부분 문자열을 탐색하는 비효율적인 방법(O(n²) 이상) 대신 선형 시간 안에 문제를 해결할 수 있습니다.