DELSORTSUB - Editorial

iceknight1093 · October 29, 2025, 4:30pm

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S.
In one operation, you can delete any sorted subsequence of S.
Find the minimum number of operations needed to make S balanced.

EXPLANATION:

A sorted binary string looks like several zeros followed by several ones, i.e., something like 000\ldots 000111\ldots 111.
In particular, note that a string with only zeros or only ones is trivially a sorted string.

This observation, combined with the fact that the empty string is balanced, immediately tells us that the answer is no more than 2.
After all, we can use one operation to delete every 0, and then a second operation to delete every 1.

Thus, we only need to check for whether the answer is either 0 or 1. If both these checks fail, the answer is surely 2.

Checking for the answer being 0 is simple: we only need to check if S is a balanced string or not.
This is a very classical problem, and can be done in linear time as follows:

Initialize a variable \text{balance} to 0.
Then, for each i from 1 to N,
- If S_i = 0, add 1 to \text{balance}.
- If S_i = 1, subtract 1 from \text{balance}.
After all N characters have been processed, S is balanced if and only if \text{balance} = 0, and \text{balance} never fell below 0 in the middle of the process.

Essentially, each 1 in the string (which can be thought of as a closing parenthesis) must be able to paired with a 0 before it (which can be thought of as an opening parenthesis). The variable \text{balance} simply holds the count of available opening parentheses we have.

Next, we need to check for the answer being 1.
That is, we want to check if deleting some subsequence of the form 000\ldots 000111\ldots 111 can make S balanced.

Now, there are seemingly too many choices for which subsequences can possibly be deleted.
However, it can be observed that we don’t actually need to care about most of them - in fact, we only need to care about subsequences of the form 00\ldots 00 or 11\ldots 11, i.e. those with all characters equal!

Why?

This is not too hard to prove.
Suppose we delete a sorted subsequence that contains both zeros and ones, and the resulting S is balanced.

Consider what happens if we hadn’t deleted the leftmost 0 and rightmost 1 instead.
Essentially, we’re inserting a 0 and a 1 back into the balanced string S, with the 0 appearing before the 1.
Since the string is balanced if and only if each 1 can be paired with a 0 before it; we can simply pair these two, and we know the remaining part is balanced anyway so they form pairs among themselves.

Alternately, we can look at how the balance check works after insertion.
If the 0 and 1 are inserted at indices i and j respectively (where i \lt j),

Till index i, nothing changes.

At i, we’re inserting a 0.
This increases the balance by 1, which is fine.

Between indices i and j, every balance increases by 1.
This is fine; since the string was balanced earlier we know all of these are \ge 0 anyway, and in fact they’ll all be \gt 0 now.

At j, the balance must reduce by 1.
This is also fine, since the insertion of the 0 earlier ensures that the current balance is \gt 0.

After j nothing changes; and we know the initial string was balanced so this will end up balanced too.

We thus have two potential choices: either delete several ones, or delete several zeros.
Let’s look at both separately.

Suppose we delete only some ones from S.
The question now is: how many ones should we delete, and which ones should we delete?

To answer that, let’s look back at our algorithm to check if S is balanced.
Note that the final value of \text{balance} simply equals the number of zeros minus the number of ones; and we wanted this to be 0 in the end.
Since we’re now only deleting ones, each such deletion (no matter where it’s done) will increase \text{balance} by exactly 1 compared to S.
Thus,

If the balance of S was initially \gt 0, deleting ones can never make it balanced.
If the balance of S was initially \le 0, we must delete exactly (-\text{balance}) ones for the balance to become 0.

Once we know the count of ones to delete, it’s easy to see that it’s best to delete the earliest-occurring ones.
That is, if k = -\text{balance}, then our best option is to delete the k leftmost ones from S and then check if the resulting string is balanced.
This, of course, can be done in linear time.

A similar analysis holds for deleting zeros: just that this time, \text{balance} zeros must be deleted; and it’s optimal to delete them from the right rather than the left.

Try both cases, and if either one works, the answer is 1; otherwise the answer is 2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)

def solve(s):
    bal, mn = 0, 0
    for c in s:
        if c == '0': bal += 1
        else: bal -= 1
        mn = min(mn, bal)
    if mn == bal:
        return 0 if mn == 0 else 1
    
    bal, mn = 0, 0
    for c in reversed(s):
        if c == '1': bal += 1
        else: bal -= 1
        mn = min(mn, bal)
    if mn == bal:
        return 0 if mn == 0 else 1
    return 2
    
for _ in range(int(input())):
    n = int(input())
    s = input()
    print(solve(s))

anusatya · October 29, 2025, 8:37pm

Good question and clear explanation. Below is solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t--> 0) {
            int n = sc.nextInt();
            char[] str = sc.next().toCharArray();

            int balance = 0;
            boolean flag = true;
            for (int i = 0; i < n; i++) {
                if (str[i] == '0') {
                    balance++;
                }
                else {
                    balance--;
                    if (balance < 0) {
                        flag = false;
                    }
                }
            }

            if (balance == 0 && flag) {
                System.out.println(0);
                continue;
            }

            if (balance > 0) {
                int excess = balance;
                //Excess 0s
                int i = n - 1;
                while (i >= 0 && excess > 0)
                {
                    if (str[i] == '0') {
                        str[i] = '-';
                        excess--;
                    }
                    i--;
                }
            }
            else {
                //Excess 1s
                int excess = -balance;
                int i = 0;
                while (i < n && excess > 0)
                {
                    if (str[i] == '1') {
                        str[i] = '-';
                        excess--;
                    }
                    i++;
                }
            }

            balance = 0;
            flag = true;
            for (int i = 0; i < n; i++) {
                if (str[i] == '0') {
                    balance++;
                }
                else if (str[i] == '1') {
                    balance--;
                    if (balance < 0) {
                        flag = false;
                    }
                }
            }

            if (balance == 0 && flag) {
                System.out.println(1);
            }
            else {
                System.out.println(2);
            }
        }
    }
}