문자열이 하나 주어졌을 때, 서로 다른 문자가 최대 k개 이하로 포함된 가장 긴 부분 문자열(substring) T의 길이를 구하는 것이 이번 문제의 목표입니다.
예를 들어 입력이 s = "eceba", k = 2라고 가정해 보겠습니다. 이 경우 정답은 3이 됩니다. 조건을 만족하는 가장 긴 부분 문자열은 "ece"이고, 그 길이가 3이기 때문입니다.
문제 해결 접근 방식: 슬라이딩 윈도우(Sliding Window)
이 문제는 슬라이딩 윈도우 기법과 해시 맵(빈도수 카운트)을 함께 사용하면 효율적으로 해결할 수 있습니다. 두 개의 포인터 i와 j를 활용해 윈도우를 확장하고 축소하면서, 항상 윈도우 내부에 서로 다른 문자가 k개 이하만 존재하도록 유지합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 정답을 저장할 변수 ans := 0으로 초기화합니다.
- 문자별 등장 횟수를 저장할 맵 m을 하나 정의합니다.
- n := 문자열 s의 길이, x := 현재 윈도우 내 서로 다른 문자의 개수(초깃값 0)로 설정합니다.
- j를 0부터 n-1까지 증가시키며 반복합니다.
- m[s[j]] 값을 1 증가시킵니다.
- 만약 m[s[j]]가 1이라면(새로운 문자가 처음 등장한 경우), x를 1 증가시킵니다.
- x > k인 동안(i <= j 조건 유지), 왼쪽 끝 문자 m[s[i]]를 1 감소시키고, 그 값이 0이 되면 x를 1 감소시킨 뒤 i를 증가시켜 윈도우를 축소합니다.
- 매 반복마다 ans와 현재 윈도우 길이(j - i + 1) 중 더 큰 값을 ans에 저장합니다.
- 반복이 끝나면 ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
};
main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}입력
"eceba", 2
출력
3
동작 과정 상세 분석
입력 "eceba"에서 k = 2일 때 알고리즘이 어떻게 동작하는지 살펴보겠습니다.
- j = 0: 'e' 추가 → 윈도우 "e" (서로 다른 문자 1개)
- j = 1: 'c' 추가 → 윈도우 "ec" (서로 다른 문자 2개)
- j = 2: 'e' 추가 → 윈도우 "ece" (서로 다른 문자 2개, 길이 3)
- j = 3: 'b' 추가 → 서로 다른 문자가 3개가 되므로 왼쪽부터 제거하여 윈도우 "ceb"로 축소
- j = 4: 'a' 추가 → 다시 축소하여 윈도우 "eba" (길이 3)
최종적으로 가장 긴 부분 문자열의 길이는 3이 반환됩니다.
시간 복잡도
포인터 j와 i는 각각 문자열을 한 번씩만 순회하므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 해시 맵에 저장되는 서로 다른 문자 수에 비례하며, 최대 O(k + 1) 수준입니다. 따라서 이 방법은 문자열이 매우 긴 경우에도 효율적으로 동작합니다.