MAKEPAL2 - EDITORIAL

editorial
,
1

PROBLEM LINK:

Contest
Practice

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)
3 Likes
2

Dude what was this question?

Like I agree that this works because the problem statement is inherently flawed but can anyone please help me out in understanding, how to print the maximum length palindrome with minimum number of delete operations given a binary string.

I am in no way a pro but want to improve so if any 4/5+ start person who knows how this can be done suggest a method of the above problem that I posed.
Like if the string is 01001, how to print 1001 and not 000.

3 Likes
3

You do not need to print 1001, you cam print any subsequence that is palindrome the only condition is that the number of deletion are less than n/2