https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

---

1. 코드

class Solution:
    """
    s = 'cbaebabacd'
    p = 'abc'

    -line11~12
    s = 'aaaaaaaaaa'
    p = 'aaaaaaaaaaaaa'
    """
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        # key 값이 될 수 있는 문자의 수는 최대 알파벳 소문자 개수인 26개이므로
        # 반복문을 사용해도 시간복잡도에 큰 영향을 주지 못한다.
        def check():
            for key in p_d:
                if key in d and p_d[key] == d[key]:
                    pass
                else:
                    return False
            return True


        ans = []
        d = defaultdict(int)
        p_d = defaultdict(int)
        for char in p:
            p_d[char] += 1

        # 0번째 인덱스부터 시작하는 슬라이딩 윈도우 초기값 설정
        for i in range(0, len(p)):
            d[s[i]] += 1
        # 0번 인덱스부터 시작인 슬라이딩 윈도우 정답 검사
        if check():
            ans.append(0)

        for start in range(1, len(s) - len(p) + 1):
            end = start + len(p) - 1
            d[s[end]] += 1
            d[s[start - 1]] -= 1
            if d[s[start - 1]] == 0:
                del d[s[start - 1]]

            if len(d) == len(p_d):
                if check():
                    ans.append(start)
        return ans

---

2. 후기

윈도우의 크기가 고정되어 있기 때문에 윈도우의 시작점과 끝점의 인덱스를 알아낼 수 있다.
슬라이딩은 시작점과 끝점에 해당하는 문자를 각각 1씩 빼주고 더해주는 방식으로 구현했다.

사전 자료형에서 사용할 수 있는 KEY값이 알파벳 소문자로 한정되어 있는 문제이다.
키값은 최대 26개 밖에 가질 수 없으므로 반복문에서 매번 모든 KEY값을 조회해도 시간복잡도에 큰 영향을 주지 못한다. 이처럼 KEY값이 한정된 문제는 자주 나오므로 반복문 사용을 주저하지 말자.