설명

예 1

입력

s0 = "abc"
s1 = "bcabxabc"

산출

3

설명

The substrings "bca", "cab" and "abc" of s0 are permutations of "abc".

직관

시간 창

구현

import java.util.*;

class Solution {
    public int solve(String s0, String s1) {
        int m = s0.length(), n = s1.length();
        if (m > n) {
            return 0;
        }
        int[] freq0 = new int[26], freq1 = new int[26];
        for (int i = 0; i < m; i++) {
            freq0[s0.charAt(i) - 'a']++;
            freq1[s1.charAt(i) - 'a']++;
        }

        int ans = 0;
        if (Arrays.equals(freq0, freq1)) {
            ans++;
        }

        for (int i = m; i < n; i++) {
            freq1[s1.charAt(i) - 'a']++;
            freq1[s1.charAt(i - m) - 'a']--;
            if (Arrays.equals(freq0, freq1)) {
                ans++;
            }
        }

        return ans;
    }
}

시간 복잡도