Codeforces Round 913 (Div. 3) |
---|
Закончено |
Влад нашёл строку $$$s$$$ из $$$n$$$ строчных латинских букв, и он хочет сделать её как можно короче.
Для этого он может любое число раз удалять из $$$s$$$ любые два соседних символа, если они различны. Например, если $$$s$$$=racoon, то удалив одну пару символов, он может получить строку coon, roon, raon и raco, но не может получить racn (потому что удалённые буквы были одинаковы) или rcon (потому что удалённые буквы не были соседними).
Какой минимальной длины может добиться Влад, применив любое число удалений?
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину строки $$$s$$$.
Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора выведите единственное число — минимальную длину строки $$$s$$$, после удаления пар соседних символов, значения которых различны.
104aabc5abaca10avbvvcvvvd7abcdefg5dabbb8aacebeaa7bbbbacc6dacfcc6fdfcdc9dbdcfbbdc
0 1 2 1 1 0 1 0 0 1
В первом наборе выходных данных примера нужно действовать следующим образом «aabc» $$$\rightarrow$$$ «ac» $$$\rightarrow$$$ «». Обратите внимание, что при другом порядке удалений строка не станет пустой.
Название |
---|