class Solution {
    // 문자열에서 모든 아나그램 찾기
    // O(s)
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        
        int[] cnt = new int[128];
        
        for (char c : p.toCharArray()) cnt[c]++;
        
        // Sliding Window with two pointers
        for (int l = 0, r = 0; r < s.length(); ++r) {
            char c = s.charAt(r);
            cnt[c]--;
            
            // 매칭되지 않으면
            while (cnt[c] < 0) { 
                // 매칭값을 원복 시키고
                cnt[s.charAt(l)]++; 
                // 왼쪽 포인터를 이동한다.
                l++;
            }
            
            // 문자열의 길이가 아나그램 문자열 길이와 같으면 p's anagram 이다. 
            if (r - l + 1 == p.length()) { 
                list.add(l);  // 시작 인덱스를 결과 리스트에 추가한다. 
            }
        }
        
        return list; 
    }
}