Count Distinct Anagram Substrings

You are given an integer k and two strings s and t consisting of lowercase English letters. It is guaranteed that t is a suffix (postfix) of s.

Your task is to count the number of distinct substrings of s with length at most k that can be rearranged to form an anagram of t.

A substring is defined as a contiguous segment of the string. Two substrings are considered distinct if they differ in content. The anagram condition means that the frequency of each letter in the substring is exactly the same as in t, i.e., if \(t\) has frequency \(f(c)\) for every character \(c\), the substring must have the same frequency counts.

Note: Even though the substring length can vary from 1 to k, only substrings whose length is equal to \(|t|\) can potentially have the same letter frequency as t (since \(|t|\) is the total number of letters in \(t\)).

inputFormat

The input is given through standard input (stdin) and consists of three lines:

1. An integer k, the maximum allowed length for a substring.
2. A string s consisting of lowercase English letters.
3. A string t consisting of lowercase English letters. It is guaranteed that t is a suffix of s.

outputFormat

Output a single integer representing the number of distinct substrings from s with length at most k that can be rearranged to form an anagram of t.

5
abbcabbc
bca

2