codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.