Perfect Substring Count
MediumSliding Window · SalesForce
A non-empty substring (a contiguous run of characters) of s is perfect if every distinct character that appears in it appears exactly k times. For example, with k = 2 the substring "abba" is perfect, while "aab" is not (b appears once) and "aaa" is not (a appears three times).
Return the number of perfect substrings of s. Substrings at different positions are counted separately even if they contain the same letters.
Example 1
- Input:
- s = "aabbab", k = 2
- Output:
- 4
- Explanation
- The perfect substrings are
aa,bb,aabbandabba(positions 1 to 4).bbabfails becausebappears three times, and the whole string has three of each letter.
Example 2
- Input:
- s = "abca", k = 1
- Output:
- 9
- Explanation
- With
k = 1a substring is perfect when no letter repeats: the 4 single letters,ab,bc,ca,abcandbca. Onlyabcarepeats a letter.
Example 3
- Input:
- s = "zzzz", k = 2
- Output:
- 3
- Explanation
- Each of the three
zzsubstrings is perfect, butzzzandzzzzcontainzmore than twice.
Constraints
- 0 ≤
s.length≤ 105 sconsists of lowercase English letters- 1 ≤
k≤ 105