codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.