Let's define the operation of compressing a string $$$t$$$, consisting of at least $$$2$$$ digits from $$$1$$$ to $$$9$$$, as follows:
For example, for a string "12345", one could do the following: split it into ("1", "23", "4", "5"), and write "235555".
Let the function $$$f(t)$$$ for a string $$$t$$$ return the minimum length of the string that can be obtained as a result of that process.
You are given a string $$$s$$$, consisting of $$$n$$$ digits from $$$1$$$ to $$$9$$$, and an integer $$$k$$$. Calculate the value of the function $$$f$$$ for all contiguous substrings of $$$s$$$ of length exactly $$$k$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$).
The second line contains the string $$$s$$$ ($$$|s| = n$$$), consisting only of digits from $$$1$$$ to $$$9$$$.
Output $$$n - k + 1$$$ integers — $$$f(s_{1,k}), f(s_{2,k+1}), \dots, f(s_{n - k + 1, n})$$$.
4 45999
14
10 31111111111
2 2 2 2 2 2 2 2
11 449998641312
12 18 17 15 12 7 7 2
Name |
---|