# PROBLEM LINK:

**Setter:** soumyadeep_21

**Testers:** tabr, tejas10p

**Editorialist:** hrishik85

# DIFFICULTY:

1393

# PREREQUISITES:

None

# PROBLEM:

Calling out the main points here that are important to the solution

- We are given a binary string S of length N
- We can remove any element from the string S. We can perform this operation
**at most**\left\lfloor \frac{N}{2} \right\rfloor times - The important point is we have to output
**any palindrome**that can be obtained in this manner. Kindly note - it can be any palindrome and doesnt specifically have to be a palindrome of the longest length

# EXPLANATION:

S is a binary string and has only **0s** and **1s**

The special constrain around removal of \left\lfloor \frac{N}{2} \right\rfloor simplifies this problem.

We just need to count the number of 0s and 1s in the original string

- If Count(1) \gt Count(0) - we can remove all the zeros and print a string containing only 1s
- If Count(0) \geq Count(1) - we can remove all the ones and print a string containing only 0s

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

## Editorialist's Solution

```
t=int(input())
for _ in range(t):
n=int(input())
S=list(input())
zero = S.count('0')
one = S.count('1')
#print(zero,one)
if zero<one:
i=0
final=str()
while i<one:
final = final + '1'
i=i+1
print(final)
if zero>=one:
i=0
final=str()
while i<zero:
final = final + '0'
i=i+1
print(final)
```