1208. Anagram Window Pairs
A genome lab slides a window of k bases along the strand s. Count the pairs of start indices i < j whose windows s[i..i+k) and s[j..j+k) are anagrams of each other, meaning they contain the same letters with the same counts. Overlapping windows are allowed to pair up.
Return the number of such pairs as a long. Slide the window while updating its 26 letter counts and an O(1)-updatable signature of them, count equal signatures in a hash map, and add C(c, 2) for each group of size c. If k is greater than s.length there are no windows and the answer is 0.
Here 1 <= s.length <= 2 * 10^5, 1 <= k <= 2 * 10^5, and s uses lowercase letters. The intended cost is O(n) time and O(n) space.
Example 1
- Input:
- s = "abab", k = 2
- Output:
- 3
- Explanation:
The windows ab, ba, ab are all anagrams of each other: 3 pairs.
Example 2
- Input:
- s = "aaaa", k = 1
- Output:
- 6
- Explanation:
The four windows are single letters a, so every pair counts: C(4, 2) = 6.
Example 3
- Input:
- s = "abcabd", k = 3
- Output:
- 3
- Explanation:
The windows abc, bca, cab, abd: the first three are anagrams of each other (3 pairs) and abd is different.
Constraints
1 ≤ s.length ≤ 2 * 105
1 ≤ k ≤ 2 * 105
s contains lowercase letters only
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)