2086: Alban's Jedi Code Decryption
题目描述
In the ancient archives of the Jedi Temple, Alban discovered a mysterious code pattern: as long as the letters P, C, K appear in order (not necessarily contiguously) within a string, it represents a valid "Jedi Code".
But a simple discovery is no longer enough for Alban's curiosity. He decides to find out how many intervals (substrings) exist such that the number of Jedi Codes appearing within that interval is no less than his Force sensitivity threshold $L$.
For example, if the threshold $L = 2$ and the string is PCCKA. In this string:
-
The 1st P, 2nd C, and 4th K form one PCK.
-
The 1st P, 3rd C, and 4th K form another PCK.
In total, there are 2 PCKs. Therefore, the intervals where the number of PCK occurrences is $\ge 2$ are [1,4] (PCCK) and [1,5] (PCCKA), for a total of 2.
Given the threshold $L$ and the string $S$, please help Alban calculate how many intervals have $\ge L$ occurrences of the Jedi Code.
输入
-
First line: The string length $N$ ($3 \leq N \leq 200,000$) and the Force sensitivity threshold $L$ ($1 \leq L \leq 10^{15}$)
-
Second line: A string $S$ of length $N$ consisting of uppercase English letters.
输出
样例输入
5 2
PCCKA
样例输出
2