 # MAKEPAL2 - EDITORIAL

Testers: tabr, tejas10p
Editorialist: hrishik85

1393

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)

3 Likes