[Solution] Make Length 1 CodeChef Solution

Problem

You are given a binary string $S$ of length $N$.

You can perform the following operation on $S$:

• Select an index $i \ (1 \leq i \lt |S|)$ such that $S_i=S_{i+1}$.
• Set $S_i$ to $0$ and remove $S_{i+1}$ from the string.

Note that after each operation, the length of $S$ decreases by $1$.

Is it possible to reduce $S$ to a single character by performing the mentioned operation exactly $N-1$ times?

Input Format

• The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• Each test case consists of two lines of input.
  • The first line of each test case contains a single integer $N$, the length of $S$.
  • The second line contains a binary string $S$ of length $N$.

Output Format

For each test case, print the answer on a new line: YES if it is possible to perform the operation $N-1$ times, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, YES, yes, yEs and yES will all be treated as identical.

Explanation:

Test case $1$: Perform the operation choosing $i = 1$. This sets $S_1 = 0$ and deletes $S_2$ from the string, after which $S$ is now a single character.

Test case $2$: It is not possible to perform any operation.

Test case $3$: One sequence of operations is as follows:

• Perform the operation on $i = 3$. Now, $S = 110$.
• Perform the operation on $i = 1$. Now, $S = 00$.
• Perform the operation on $i = 1$. Now, $S = 0$ and we are done.

Test case $4$: It is not possible to perform any operation.