DMPG '18 B5 - Mimi and Substrings - DMOJ: Modern Online Judge

DMPG '18 B5 - Mimi and Substrings

Points: 7 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mimi is playing with a string $S$ ~S~ when her little sister asks her a question:

How many substrings of $S$ ~S~ are there such that these substrings are of length $K$ ~K~ and have exactly 1 distinct letter?

Constraints

Let $|S|$ ~|S|~ denote the length of $S$ ~S~.

For all subtasks, $1 \le K \le |S|$ ~1 \le K \le |S|~.

Subtask 1 [10%]

$1 \le |S| \le 2\,000$ ~1 \le |S| \le 2\,000~

Subtask 2 [90%]

$1 \le |S| \le 1\,000\,000$ ~1 \le |S| \le 1\,000\,000~

Input Specification

The first line of input will contain a single string, $S$ ~S~, consisting of only lowercase English letters.
The second line of input will contain an integer, $K$ ~K~.

Output Specification

The number of substrings which satisfy the given condition.

Sample Input

aaaabb
2

Sample Output

Comments

There are no comments at the moment.