문자열 S가 주어졌을 때, 중복되는 문자가 하나도 없는 길이 K의 부분 문자열이 몇 개 존재하는지 구하는 문제입니다.
예를 들어 S = "heyfriendshowareyou"이고 K = 5라면, 조건을 만족하는 부분 문자열은 다음과 같이 총 15개입니다.
[heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou]
해결 접근 방식: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자별 등장 횟수를 저장하는 맵(딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 윈도우를 오른쪽으로 확장하다가 중복 문자가 발견되면 왼쪽 경계를 밀어내는 방식입니다.
알고리즘 단계
- 빈 맵 m을 생성하고, left := 0, right := -1, ans := 0으로 초기화합니다.
- right가 문자열 길이 - 1보다 작은 동안 반복합니다.
- 만약 right - left + 1 = k라면 (윈도우 크기가 k에 도달한 경우)
- ans를 1 증가시킵니다.
- m[str[left]] 값을 1 감소시킵니다.
- left를 1 증가시키고 다음 반복으로 넘어갑니다.
- 만약 str[right + 1]이 맵에 없다면
- m[str[right + 1]] := 1로 설정합니다.
- right를 1 증가시킵니다.
- 그렇지 않고 m[str[right + 1]]이 0이라면 (이전에 등장했지만 현재 윈도우에는 없는 경우)
- m[str[right + 1]]을 1 증가시킵니다.
- right를 1 증가시킵니다.
- 그 외의 경우 (중복 문자가 윈도우 내에 존재하는 경우)
- m[str[left]]를 1 감소시킵니다.
- left := left + 1로 갱신합니다.
- 만약 right - left + 1 = k라면 (윈도우 크기가 k에 도달한 경우)
- 반복 종료 후 right - left + 1 = k라면 ans를 1 증가시킵니다.
- ans를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def numKLenSubstrNoRepeats(self, S, K):
m = {}
left = 0
right = -1
ans = 0
while right < len(S) - 1:
if right - left + 1 == K:
ans += 1
m[S[left]] -= 1
left += 1
continue
if S[right + 1] not in m:
m[S[right + 1]] = 1
right += 1
elif not m[S[right + 1]]:
m[S[right + 1]] += 1
right += 1
else:
m[S[left]] -= 1
left += 1
if right - left + 1 == K:
ans += 1
return ans
ob1 = Solution()
print(ob1.numKLenSubstrNoRepeats("heyfriendshowareyou", 5))입력
"heyfriendshowareyou" 5
출력
15
복잡도 분석
- 시간 복잡도: O(N) — left와 right 포인터가 각각 문자열을 한 번씩만 순회하므로 선형 시간에 해결됩니다.
- 공간 복잡도: O(K) — 맵에는 최대 윈도우 크기 K개의 문자 정보만 저장됩니다.
단순히 모든 부분 문자열을 검사하는 브루트포스 방식(O(N×K))보다 슬라이딩 윈도우 기법이 훨씬 효율적이며, 특히 문자열이 길어질 때 그 차이가 두드러집니다.