# PROBLEM LINK:

Practice

Div-2 Contest

Div-1 Contest

* Author:* Ashish Gupta

*Rahul Dugar*

**Tester:***Mohammed Ehab*

**Editorialist:**# DIFFICULTY:

SIMPLE

# PREREQUISITES:

None

# PROBLEM:

Given a binary string, what’s the minimum number of characters you need to remove to make it non-decreasing?

# QUICK EXPLANATION:

For every index i, try erasing all the 1's up to i and all the 0's after it. The answer is the minimum across all i.

# EXPLANATION:

For a binary string to be non-decreasing, it has to start with a bunch of 0's and then end with a bunch of 1's. So how can you make your string non-decreasing? Start with fixing the “split index,” the index where you’ll change from 0's to 1's; let’s call it i. You need to erase all the 1's that come before i and all the 0's that come after it. You can pre-compute these quantities using prefix-sum arrays. Now, to get the answer, just try every i to be the split index and take the minimum across them.

Bonus task: what if it’s a ternary string? Can you still solve in linear time?

# SOLUTIONS:

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
int pre[100005],suf[100005];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
string s;
cin >> n >> s;
for (int i=1;i<=n;i++)
pre[i]=pre[i-1]+(s[i-1]=='1');
suf[n]=0;
for (int i=n-1;i>=0;i--)
suf[i]=suf[i+1]+(s[i]=='0');
int ans=n;
for (int i=0;i<=n;i++)
ans=min(ans,pre[i]+suf[i]);
printf("%d\n",ans);
}
}
```