DELNQ - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have a binary string. In one move, you can delete two adjacent unequal characters and delete any one of them.
Find the minimum possible length of the final string.

EXPLANATION:

If S contains only zeros, or only ones, it’s not possible to make a move at all.
In these two cases, the answer is always N.

If S contains both zeros and ones, it’s always possible to reduce the length to 1.
A simple strategy to do this is as follows:

  • Since S contains at least one 0 and at least one 1, there must be a 0 adjacent to a 1. Pick some such pair of adjacent unequal characters.
  • Then, if there are more zeros in S, delete the 0. Otherwise, delete the 1.

Since we delete whichever character appears more often, S will still contain both zeros and ones after the deletion meaning the process can be repeated.
This will only stop when there’s exactly one each of zeros and ones in S, at which point deleting one of them will leave us with a length 1 string as claimed.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    if min(s) == max(s): print(n)
    else: print(1)