[Neetcode/Sliding Window] Permutation in String

https://neetcode.io/problems/permutation-string

NeetCode

🛠 해결 전략

이 문제는 슬라이딩 윈도우(Sliding Window) + 해시맵(딕셔너리) 활용으로 O(n)에 해결할 수 있다.

1. s1의 모든 문자 빈도 수를 계산 (char_count_s1).
2. s2에서 길이가 len(s1)인 윈도우를 이동하며 같은 빈도 수를 갖는지 비교 (char_count_window).
3. 첫 번째 윈도우 확인 후 한 칸씩 이동하며 검사
4. 만약 동일한 빈도 수를 가지는 구간이 있다면 True 반환.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n, m = len(s1), len(s2)
        
        if n > m:  # s1이 s2보다 길면 불가능
            return False
        
        # 1️⃣ s1의 문자 빈도수 계산
        char_count_s1 = Counter(s1)
        
        # 2️⃣ s2에서 처음 `n` 길이의 윈도우 문자 빈도수 계산
        char_count_window = Counter(s2[:n])

        # 3️⃣ 첫 번째 윈도우가 정답인지 확인
        if char_count_window == char_count_s1:
            return True

        # 4️⃣ 슬라이딩 윈도우 이동
        for i in range(n, m):
            # 새로 추가된 문자 => 새로운 문자 추가
            char_count_window[s2[i]] += 1
            # 제거되는 문자 => 왼쪽 끝 문자 제거
            char_count_window[s2[i - n]] -= 1

            # 현재 윈도우 빈도수와 s1 빈도수 비교
            if char_count_window == char_count_s1:
                return True
        
        return False

⏳ 시간 복잡도 분석

• 초기 Counter(s1), Counter(s2[:n]) 계산: O(n)
• 슬라이딩 윈도우 이동: O(m - n)
• 총 시간 복잡도: O(n) + O(m - n) = O(m)

💡 즉, O(m)의 시간 복잡도로 매우 빠르게 해결 가능!