PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You have a binary string S.
You can:
- Choose i such that S_i \ne S_{i+1}
- Keep either the prefix till i or the suffix from i+1, and discard the other part.
- The part that’s kept must contain both 0’s and 1’s.
This operation can be performed however many times you like.
Find the lexicographically smallest string S that’s reachable.
EXPLANATION:
If no operation can be performed, obviously the answer is S itself.
So, the only interesting case is when an operation can be performed at all - which means there must be an index i such that S_i \ne S_{i+1} and either the first i characters contain both 0 and 1, or the last N-i characters contain both 0 and 1.
To analyze this, it’s helpful to look at the string in terms of blocks.
Here, a block is a maximal contiguous substring containing the same character, i.e. for S = 100111011 the blocks are \{1, 00, 111, 0, 11\}.
Note that the characters of the blocks always alternate between 0 and 1 as we move left to right.
Since we can only choose an index i such that S_i \ne S_{i+1}, we’re really only able to cut the string “between” two blocks.
So, the condition that the part we keep after cutting must contain both 0’s and 1’s, just means that the part we keep must contain at least two blocks (the block values alternate so having \ge 2 blocks means we’ll have both zeros and ones; while having only one block means we have only a single character type.)
In particular, observe that the final string we end up with must also have at least two blocks (given that we start from a string with \ge 2 blocks in the first place.)
Further, it’s in fact optimal for the final string to have exactly two blocks - because if we have a string with more than two blocks, we can always cut it just after the second block and keep only the first two blocks; giving us a strictly smaller prefix of what we previously had (and this prefix is of course lexicographically smaller than the larger string.)
The question now is, which two blocks should this be?
To answer that, we look at lexicographic minimization.
First, clearly it’s optimal for the string to start with 0, rather than start with 1.
So, the first block must contain zeros, while the second must contain ones.
Next, among all blocks containing zeros, it’s optimal for the block to be as large as possible, i.e. to maximize the number of zeros.
This is because we’re guaranteed to have a 1 after the block of zeros; so if we chose a shorter zero-block then it would have a 1 at an earlier position as opposed to a longer zero-block.
Thus, the zero-block length should be maximized.
Finally, among all maximum-length zero-blocks, the one-block immediately after it should be as short as possible.
This is because a shorter one-block will be a prefix of a longer one-block, and hence lexicographically smaller.
So, the eventual solution is quite simple:
- Compute the blocks of S.
- If no operation can be performed (i.e. S has \le 2 blocks initially), the answer is just S.
- Otherwise, pick the longest possible zero-block.
- Note that if the last block of S is a zero-block, it’s not allowed to pick it; since there’s no one-block after it.
- Among all maximum length zero-blocks, find the shortest one-block immediately after it.
These two blocks together will form the answer.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
blocks = []
cur, lt = s[0], 0
for c in s:
if c == cur: lt += 1
else:
blocks.append((cur, lt))
lt = 1
cur = c
blocks.append((cur, lt))
if len(blocks) <= 2: print(s)
else:
x, y = 0, 0
for i in range(len(blocks)-1):
if blocks[i][0] == '1': continue
if blocks[i][1] > x:
x = blocks[i][1]
y = blocks[i+1][1]
elif blocks[i][1] == x:
y = min(blocks[i+1][1], y)
print('0'*x + '1'*y)