1105B.md (1966B)
1 Source: https://codeforces.com/problemset/problem/1105/B 2 3 B. Zuhair and Strings 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given a string $s$ of length $n$ and integer $k$ ($1 \le k \le n$). The string $s$ has a level $x$, if $x$ is largest non-negative integer, such that it's possible to find in $s$: 22 23 * $x$ non-intersecting (non-overlapping) substrings of length $k$, 24 * all characters of these $x$ substrings are the same (i.e. each substring contains only one distinct character and this character is the same for all the substrings). 25 26 A substring is a sequence of consecutive (adjacent) characters, it is defined by two integers $i$ and $j$ ($1 \le i \le j \le n$), denoted as $s[i \dots j]$ = "$s_{i}s_{i+1} \dots s_{j}$". 27 28 For example, if $k = 2$, then: 29 30 * the string "aabb" has level $1$ (you can select substring "aa"), 31 * the strings "zzzz" and "zzbzz" has level $2$ (you can select two non-intersecting substrings "zz" in each of them), 32 * the strings "abed" and "aca" have level $0$ (you can't find at least one substring of the length $k=2$ containing the only distinct character). 33 34 Zuhair gave you the integer $k$ and the string $s$ of length $n$. You need to find $x$, the level of the string $s$. 35 36 Input 37 38 The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string and the value of $k$. 39 40 The second line contains the string $s$ of length $n$ consisting only of lowercase Latin letters. 41 42 Output 43 44 Print a single integer $x$ — the level of the string. 45 46 Examples 47 48 Input 49 50 ``` 51 8 2 52 aaacaabb 53 ``` 54 55 Output 56 57 ``` 58 2 59 ``` 60 61 Input 62 63 ``` 64 2 1 65 ab 66 ``` 67 68 Output 69 70 ``` 71 1 72 ``` 73 74 Input 75 76 ``` 77 4 2 78 abab 79 ``` 80 81 Output 82 83 ``` 84 0 85 ``` 86 87 Note 88 89 In the first example, we can select $2$ non-intersecting substrings consisting of letter 'a': "(aa)ac(aa)bb", so the level is $2$. 90 91 In the second example, we can select either substring "a" or "b" to get the answer $1$.