CSES - Putka Open 2020 – 3/5 - ABC-poisto
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Annettuna on merkkijono, jonka jokainen merkki on A, B tai C. Saat poistaa joka askeleella kaksi vierekkäistä merkkiä, jotka eivät ole samat. Montako merkkiä voit poistaa enintään?

Esimerkiksi kun merkkijono on CABAC, voit poistaa enintään 44 merkkiä. Yksi optimaalinen ratkaisu on poistaa ensin merkit AB, jolloin merkkijonosta tulee CAC, ja sitten merkit CA, jolloin merkkijonosta tulee C.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku tt: testien määrä.

Tämän jälkeen tulee tt riviä, joista jokainen sisältää yhden merkkijonon. Merkkijonossa on nn merkkiä ja jokainen merkki on A, B tai C.

Tuloste

Tulosta jokaisesta testistä, montako merkkiä voit poistaa enintään.

Esimerkki

Syöte:

4
AB
CABAC
AAAA
AABBCC

Tuloste:

2
4
0
6

Osatehtävä 1 (42 pistettä)

  • 1t1001 \le t \le 100
  • 1n101 \le n \le 10

Osatehtävä 2 (58 pistettä)

  • 1t1001 \le t \le 100
  • 1n1001 \le n \le 100