Anagram Substrings

Description

Given two strings s0 and s1, return the number of substrings where s1 contains any anagram of s0.

Constraints:

• n ≤ 100,000 where n is the length of s0
• m ≤ 100,000 where m is the length of s1

Example 1

Input

s0 = "abc"
s1 = "bcabxabc"

Output

3

Explanation

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

---

---

Intuition

Time Window

1. the length of window is same as s0
2. so we can init two arrays, one for s0, another for s1
3. and then move s1's window step by step and compare it with s0's window

Implementation

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;
    }
}

Time Complexity

• Time: O(M*N)
• Space: O(1)