1303. Shared Anagram Windows
Two strings, s and t, describe the letter patterns on two shelves of tiles, and k is a window length. A window of s is matched when some length-k window of t contains exactly the same letters with the same counts, in any order. Count the start positions i, from 0 up to the length of s minus k, whose window s[i..i+k-1] is matched. If k is larger than the length of either string there are no windows to compare and the answer is 0. Slide a fixed 26-letter count along t and store the count signature of every window in a hash set, then slide along s and look each signature up. Target O(26 * (n + m)) time for string lengths n and m.
Example 1
- Input:
- s = "abcab", t = "bcaxx", k = 3
- Output:
- 3
- Explanation:
All three windows of s (abc, bca, cab) are anagrams of the window bca in t, so the count is 3.
Example 2
- Input:
- s = "aab", t = "baa", k = 2
- Output:
- 2
- Explanation:
The windows of s are aa and ab; aa equals the window aa of t and ab is an anagram of ba, so the count is 2.
Example 3
- Input:
- s = "xyz", t = "abc", k = 1
- Output:
- 0
- Explanation:
No single letter of s appears anywhere in t, so no window matches and the answer is 0.
Constraints
1 ≤ s.length, t.length ≤ 1000
1 ≤ k ≤ 1000
s and t contain only lowercase letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(26 * (n + m))
- Space
- O(26 * m)