DMPG '18 B5 - Mimi and Substrings

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.8s
Memory limit: 256M

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 when her little sister asks her a question:

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


Let |S| denote the length of S.

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

Subtask 1 [10%]

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

Subtask 2 [90%]

1 \le |S| \le 1\,000\,000

Input Specification

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

Output Specification

The number of substrings which satisfy the given condition.

Sample Input


Sample Output



There are no comments at the moment.