Maximizing jz Substrings with Limited Swaps

Problem Statement:

LHX’s mentor recently arrived in X City to guide OI training. Along one road, a group of supporters wearing cultural T-shirts with big characters gathered to welcome the mentor. To simplify the depiction of the dissonant lineup, we replace the characters “教” and “主” with the letters (j) and (z) respectively. Thus, the current queue is represented as a sequence consisting of the letters (j) and (z). In order to make the mentor as comfortable as possible, you are allowed to adjust the queue by swapping any two characters. Your goal is to maximize the number of occurrences of the substring (jz) (i.e. an adjacent pair where the first character is (j) and the second is (z)).

You are allowed at most (K) swaps. Note that in one swap you may choose any two positions in the sequence and exchange their characters. For example, if the final sequence is "jzjz", then the (jz) substrings appear at positions 1–2 and 3–4, giving a total of 2 occurrences.

Input Format: The first line contains two integers (n) and (K), where (n) is the length of the sequence and (K) is the maximum number of swaps allowed. The second line contains a string of length (n) consisting only of the characters (j) and (z).

Output Format: Output a single integer, the maximum number of consecutive (jz) substrings that can be obtained after at most (K) swaps.

All formulas are given in (\LaTeX) format.

inputFormat

The input consists of two lines. The first line contains two integers (n) and (K). The second line contains a string of (n) characters (each character is either (j) or (z)).

outputFormat

Output a single integer representing the maximum number of consecutive (jz) substrings possible after performing at most (K) swaps.

sample

2 0
jz

1