Noir et Blanc


Submit solution

Points: 30 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C++, Java, Python

C'est l'heure du déjeuner pour Sami. Son ami Amine, lui a préparé un jeu difficile à jouer en mangeant.

Amine a un appareil avec n touches consécutives, pour chaque clic sur une touche, il y a deux résultats: soit la touche devient noire ou blanche.

Une partie de jeu peut être considérée comme une séquence de n touches colorées.

pour le jeu, Sami peut effectuer au plus K opérations (éventuellement zéro) sur l'appareil.

Une opération consiste à choisir un intervalle \([l, r]\) et à inverser la couleur des touches contenus dans cet intervalle. Autrement dit, pour chaque \(i = l, l + 1, ..., r\), la touche \(i\) deviendra noire si elle était blanche et vice versa.

Amine a demandé à son ami Sami de trouver le nombre maximum de touches consécutives de couleur noire après au plus \(k\) opérations.

Spécification d'entrée

La première ligne du fichier d'entrée contient \(T\) le nombre de cas de tests.

Chaque cas de test commence par une ligne qui contient deux entiers (\(1 \leq N \leq 10^5 \)) et (\(1 \leq K \leq 10^5 \)) - Le nombre de touches dans l'appareil et le nombre maximum d'opérations autorisées.

La ligne suivante contient une chaîne de caractères de longueur \( N \) représentant l'état de l'appareil avant de lancer le défi. Chaque caractère de la chaîne est soit 'N' soit 'B'. Le caractère 'B' représente la couleur blanche et le caractère 'N' représente la couleur noire.

Spécification de sortie

Pour chaque cas de test, afficher un entier : le nombre maximum de touches noirs consécutives après au plus k opérations.

Scoring

  • \( K = 1 \) et \( N \leq 1000 \) (\(15\) points).
  • \( K > N/2 \) (\(15\) points).
  • \( K=1 \) (\(30\) points).
  • Pas de contrainte additionnelle (\(40 \) points).

Sample Input

3
5 2
BBNBN
6 1
BBNNBB
1 1
B

Sample Output

5
4
1

Comments

There are no comments at the moment.