- 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 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 : testien määrä.
Tämän jälkeen tulee riviä, joista jokainen sisältää yhden merkkijonon. Merkkijonossa on 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