2241C.md (2706B)
1 Source: https://codeforces.com/problemset/problem/2241/C 2 3 C. RemovevomeR 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary string $s$ consisting only of the characters $\texttt{0}$ and $\texttt{1}$. 22 23 In one operation, you can do the following: 24 25 * Choose a substring$^{\text{∗}}$ of $s$ that is a palindrome$^{\text{†}}$ of length at least $2$. 26 * Delete exactly one character from this chosen substring. 27 28 The remaining parts of the string are then concatenated to form the new string $s$. 29 30 Find the minimum possible length of the string $s$ that can be achieved after applying this operation any number of times (possibly zero). 31 32 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. 33 34 $^{\text{†}}$A string $a$ of length $m$ is said to be palindrome if $a_i = a_{m + 1 - i}$ for all $1 \le i \le m$. 35 36 Input 37 38 The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of each test case follows. 39 40 The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the binary string $s$. 41 42 The second line of each test case contains a binary string $s$ of length $n$. It is guaranteed that each character of $s$ is either $\texttt{0}$ or $\texttt{1}$. 43 44 Output 45 46 For each test case, print the minimum possible length of the string $s$ that can be achieved after applying the operation any number of times. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 4 56 57 0000 58 59 3 60 61 110 62 63 6 64 65 110011 66 67 6 68 69 101100 70 ``` 71 72 Output 73 74 ``` 75 1 76 77 2 78 79 1 80 81 1 82 ``` 83 84 Note 85 86 In the first test case, the initial string is $\texttt{0000}$. We can perform the following sequence of operations: 87 88 * Choose the palindromic substring $\texttt{0000}$. Delete one $\texttt{0}$. The string becomes $\texttt{000}$. 89 * Choose the palindromic substring $\texttt{000}$. Delete one $\texttt{0}$. The string becomes $\texttt{00}$. 90 * Choose the palindromic substring $\texttt{00}$. Delete one $\texttt{0}$. The string becomes $\texttt{0}$. 91 92 The string $\texttt{0}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $1$. 93 94 In the second test case, the initial string is $\texttt{110}$. 95 96 * Choose the palindromic substring $\texttt{11}$. Delete one $\texttt{1}$. The string becomes $\texttt{10}$. 97 98 The string $\texttt{10}$ contains no palindromic substrings of length at least $2$, so no further operations can be performed. The minimum possible length is $2$.