LeetCode

LeetCode 567 Permutation in String 풀이: 문자 빈도 슬라이딩 윈도우

2026년 9월 28일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 567. Permutation in String
출처: LeetCode
학습: 슬라이딩 윈도우 학습 가이드
자체 판단 난이도: Level 3

두 문자열의 문자 빈도를 비교하며 s2에서 고정 길이의 연속 구간을 이동한다. 창에서 나가고 들어오는 문자의 빈도를 갱신하고 길이 조건도 지켜야 하므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

문자열 s1, s2가 주어질 때 s2 안에 s1의 순열과 같은 부분 문자열이 있으면 True, 없으면 False를 반환한다.

순열은 문자의 순서만 다르고 각 문자의 개수는 같아야 한다. 길이가 len(s1)인 구간을 확인해 문자별 빈도가 s1과 일치하는지 비교하면 된다.

조건은 다음과 같다.

s1, s2의 길이는 각각 1 이상 10^4 이하입니다.
두 문자열은 소문자 영문자 a부터 z로만 구성된다.
찾아야 하는 것은 부분수열이 아니라 연속된 부분 문자열입니다.
s1보다 짧은 부분 문자열은 순열이 될 수 없다.

예를 들어 s1 = "ab", s2 = "eidbaooo"이면 s2 안의 부분 문자열 "ba"가 "ab"의 순열이므로 True입니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

고정 길이 윈도우와 문자 빈도

s1의 길이를 window_size라고 하고, s2에서 같은 길이의 연속 구간을 유지한다. 소문자 영문자는 26종이므로 각 문자의 개수를 길이 26인 배열에 저장한다.

required[i]: s1에서 알파벳 i가 등장하는 횟수
window[i]: 현재 s2 윈도우에서 알파벳 i가 등장하는 횟수

두 배열이 같으면 현재 윈도우는 s1의 순열입니다. 빈도 배열의 비교는 26칸만 확인하므로 입력 크기와 관계없이 상수 시간입니다.

고정 창에서 바뀌는 두 문자만 갱신하기

순열 여부는 문자의 순서가 아니라 빈도로 결정된다. 따라서 윈도우 안의 순열을 모두 만들거나 각 부분 문자열을 정렬할 필요가 없다.

윈도우를 오른쪽으로 한 칸 옮길 때 전체 빈도를 다시 세지 않고 두 문자만 갱신한다.

새로 들어오는 s2[right]의 빈도를 1 증가시킵니다.
창에서 빠져나가는 s2[right - window_size]의 빈도를 1 감소시킵니다.
갱신한 빈도 배열을 required와 비교한다.

상태 전이와 경계 처리

먼저 len(s1) > len(s2)이면 들어갈 창이 없으므로 False를 반환한다. 그렇지 않으면 첫 윈도우의 빈도를 만들어 비교하고, 오른쪽 문자를 하나씩 추가하며 창 길이를 유지한다.

반복은 right를 len(s1)부터 len(s2) - 1까지 이동한다. 매번 이전 창의 왼쪽 문자를 제거해야 창 길이가 len(s1)로 유지된다.

오답 접근과 반례

문자 종류만 같고 개수가 다른 경우를 순열로 오인하면 안 된다.

s1 = "aab"
s2 = "abb"

두 문자열은 모두 a, b를 포함하지만 빈도는 각각 a:2, b:1과 a:1, b:2입니다. 따라서 "abb"는 "aab"의 순열이 아니며 정답은 False입니다. 집합으로 문자 종류만 비교하지 말고 빈도 전체를 비교해야 한다.

모든 부분 문자열을 매번 잘라 정렬하면 겹치는 창의 정보를 재사용하지 못한다. s2의 길이는 최대 10^4이므로 고정 길이 윈도우에서 바뀐 두 문자만 갱신하는 편이 효율적이다.

시간·공간 복잡도

초기 빈도를 만드는 데 O(m)이 걸리고, s2를 한 번 훑으며 각 창에서 26개 칸을 비교한다. 문자 집합 크기 26은 상수이므로 전체 시간 복잡도는 O(n + m)이며, 여기서 m = len(s1), n = len(s2)입니다. 빈도 배열 두 개의 크기는 각각 26으로 고정되어 추가 공간 복잡도는 O(1)입니다.

3. 문제 해결 코드 (Python)

required에는 s1의 빈도를, window에는 현재 창의 빈도를 저장한다. 창을 한 칸 움직일 때 빠지는 문자와 들어오는 문자만 갱신하므로 전체 문자열을 다시 세지 않는다.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window_size = len(s1)
        if window_size > len(s2):
            return False

        required = [0] * 26
        window = [0] * 26

        for index in range(window_size):
            required[ord(s1[index]) - ord("a")] += 1
            window[ord(s2[index]) - ord("a")] += 1

        if window == required:
            return True

        for right in range(window_size, len(s2)):
            entering = ord(s2[right]) - ord("a")
            leaving = ord(s2[right - window_size]) - ord("a")

            window[entering] += 1
            window[leaving] -= 1

            if window == required:
                return True

        return False

반복문에 들어가기 전에 첫 윈도우를 비교해야 s2의 앞부분에 답이 있는 경우도 놓치지 않는다. 이후에는 들어오는 문자와 나가는 문자의 인덱스만 계산해 빈도를 갱신한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 순열 포함, 불포함, 반복 문자 빈도를 확인할 수 있다.

solver = Solution()
assert solver.checkInclusion("ab", "eidbaooo") is True
assert solver.checkInclusion("ab", "eidboaoo") is False
assert solver.checkInclusion("aab", "abb") is False

4. 공식 예제와 추가 검증

작성한 checkInclusion 함수를 Python으로 실행해 공식 예제와 빈도·길이 경계 사례를 확인했다.

공식 예제

입력	기대 출력	확인 결과
`s1 = "ab", s2 = "eidbaooo"`	`True`	통과
`s1 = "ab", s2 = "eidboaoo"`	`False`	통과

추가 검증 1: `s1`이 `s2`보다 긴 경우

입력: s1 = "abcd", s2 = "abc"
기대 출력: False
확인 결과: 통과
검증 목적: 가능한 고정 길이 창이 없을 때 즉시 종료하는지 확인

추가 검증 2: 중복 문자의 빈도까지 일치하는 경우

입력: s1 = "aabc", s2 = "eidbaacoo"
기대 출력: True
확인 결과: 통과
검증 목적: 순서와 무관하게 중복 문자의 개수까지 일치하는 창을 찾는지 확인

추가 검증 3: 문자 종류만 같고 빈도가 다른 경우

입력: s1 = "aab", s2 = "abb"
기대 출력: False
확인 결과: 통과
검증 목적: 문자 집합이 아니라 빈도 배열을 비교하는지 확인

추가 검증 4: 최대 길이에 가까운 창

입력: s1 = "a" * 5000, s2 = "b" * 5000 + "a" * 5000
기대 출력: True
확인 결과: 통과
검증 목적: 길이 10,000의 문자열을 선형으로 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

Permutation in String 공식 문제는 s2 안에 s1의 순열인 부분 문자열이 있는지 묻는다.
NeetCode의 Permutation in String 설명은 부분 문자열 정렬, 문자 빈도 비교, 고정 길이 슬라이딩 윈도우를 비교한다.

정렬 기반 풀이는 길이 m인 각 윈도우를 정렬해 s1과 비교할 수 있지만, 매번 정렬하므로 비효율적이다. 빈도 배열은 알파벳이 26자로 제한된 조건을 활용해 비교 공간을 상수로 유지한다.

이 풀이는 빈도가 일치하는 문자 수를 따로 세지 않고 26칸 배열 전체를 비교한다. 알파벳 크기가 고정되어 있어 구현은 단순하고 시간 복잡도는 O(n + m)이다.

마무리

Permutation in String는 순열을 직접 만들지 않고 문자 빈도를 비교하는 문제다. s1과 같은 길이의 윈도우를 s2에서 이동하며 나가는 문자와 들어오는 문자만 갱신하면 된다. 소문자 알파벳이 26종이라는 조건을 활용해 O(n + m) 시간과 O(1) 추가 공간에 해결할 수 있다.