SSUBSTR - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: Jeevan Jyot Singh
Testers: Nishank Suresh, Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

1310

PREREQUISITES:

Observation

PROBLEM:

You have a binary string S of length N. In one move, you can delete any sorted substring of S. Find the minimum number of deletions to obtain a sorted string.

EXPLANATION:

Deleting a sorted substring means we delete either:

  • A substring whose characters are all the same; or
  • A substring that looks like 000\ldots 000111\ldots 111

This also tells us that the final string must be of this form. In particular, a binary string is sorted if and only if it doesn’t contain 10 as a subsequence, so our aim is to remove all such subsequences.

We can now make a few observations:

  • One simple observation we can make is that if S_i = S_{i+1} for some index i, then in any solution either both these characters must be deleted, or they both can be left alive. (do you see why?)
    • This allows us to essentially ‘compress’ the string by considering only adjacent unequal characters, i.e, make the string look like either 101010\ldots or 010101\ldots
  • From now on, we’ll only consider such compressed strings. Note that they will be alternating.
  • If the first character is 0, we can just leave it alone and never delete it, since it’ll never affect sortedness. So, we can assume that the first character is always 1.
  • Similarly, if the last character is 1, we can leave it alone. So, we can assume the last character is always 0.

Now note that we are in a case where we have an alternating binary string, whose first character is 1 and last character is 0. This means it must look like 1010\ldots10, and in particular has even length, say 2K.
The minimum number of moves needed to sort such a string is simply K.

Proof

K is clearly an upper bound — you can use K moves to remove all the K ones, leaving only the zeros which are sorted.

On the other hand, we also always need at least K moves.
Let’s break the string into K substrings, each of the form 10. Note that either a 1 or a 0 (or potentially both) must be deleted from each of these substrings: leaving both alive would make the final string non sorted.

Now, let’s look at our possible moves. Since the substring chosen must be sorted, we have only 3 options:

  • Choose a 0
  • Choose a 1
  • Choose a 01

If we choose a 01, we simply end up in the same situation but with length 2K-2 instead.
So, let’s look at the case when we can only delete a 0 or a 1.

As noted above, we have K substrings of the form 10 that all need to be broken. With one character being deleted per move, we obviously need at minimum K moves to break all these substrings, giving us our lower bound.

The final solution is thus to compress the input string into an alternating binary string, delete the first character (if it is 0) and/or last character (if it is 1), and then print half the length of the obtained string.

Note that this is also simply the number of times 10 appears as a substring of S, which is an easy way to implement the solution.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    input()
    print(input().count('10'))
1 Like