Background

The first Platinum problem of the USACO January 2019 contest.

Problem Description

The cows’ megacity, Cowopolis, is going to be redistricted! This is always a controversial political event between the two main groups living here (Holsteins and Guernseys), because both groups want to keep enough influence in the Cowopolis government.

The Cowopolis metropolitan area consists of a line of $n$ pasture blocks, each containing one cow, which is either a Holstein or a Guernsey.

The Cowopolis government wants to divide the metropolitan area into several contiguous districts, such that each district contains at least one pasture block and at most $k$ pasture blocks, and each pasture block belongs to exactly one district. Since the government is currently controlled by Holsteins, they want to find a redistricting plan that minimizes the number of districts where Guernseys are in the majority or the district is tied (a district is tied if the number of Guernseys equals the number of Holsteins).

A politically concerned Guernsey group wants to know how much damage the government’s redistricting plan could do to them. Help them find the worst case, i.e., the minimum possible number of districts where Guernseys have a majority or the district is tied.

Input Format

The first line contains two integers separated by spaces, representing the number of pasture blocks $n$ and the maximum number of pasture blocks in each district $k$.

The second line contains a string $s$ of length $n$, consisting only of the characters H and G. If the $i$-th character of $s$ is H, then the cow on the $i$-th pasture block is a Holstein; otherwise, it is a Guernsey.

Output Format

Output one integer on one line, representing the minimum possible number of districts where Guernseys are in the majority or the district is tied.

7 2
HGHGGHG

3

Hint

Sample Explanation

One possible partition is $[1],~[2, 3],~[4, 5],~[6, 7]$. The second and fourth districts are tied, and the third district has a Guernsey majority.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq k \leq n \leq 3 \times 10^5$, the length of $s$ is $n$, and $s$ contains only the characters H and G.

Translated by ChatGPT 5