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);
}
}
Below is my code for the bonus question. I first calculate the cost of making s[0,…,i] into a 0-1 string for each i. Then the answer would be minimum of cost of making s[0,…,i] into a 0-1 string + number of zeroes and ones in s[i+1,…,n-1] over all i.
Note : This code works for the original problem as well.
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
char s[n+1];
s[0]='0'; //doesn't alter the answer. Just makes writing the code easier.
for(int i=1;i<=n;i++)
{
cin>>s[i];
}
int count_0[n+1]={0};
int count_1[n+1]={0};
int count_2[n+1]={0};
count_0[0]=1;
for(int i=1;i<=n;i++)
{
count_0[i]=count_0[i-1];
count_1[i]=count_1[i-1];
count_2[i]=count_2[i-1];
if(s[i]=='0') count_0[i]++;
if(s[i]=='1') count_1[i]++;
if(s[i]=='2') count_2[i]++;
}
int cost_to_make_a_0_1_string_till_here[n+1]={0};
int minimum_1_minus_0=1e9;
for(int i=1;i<=n;i++)
{
cost_to_make_a_0_1_string_till_here[i]=min(count_0[i]+count_2[i],count_1[i]+count_2[i]);
if(s[i]=='1') minimum_1_minus_0=min(minimum_1_minus_0,count_1[i-1]-count_0[i-1]);
cost_to_make_a_0_1_string_till_here[i]=min(cost_to_make_a_0_1_string_till_here[i],minimum_1_minus_0+count_0[i]+count_2[i]);
}
int ans=1e9;
for(int i=0;i<=n;i++)
{
ans=min(ans,cost_to_make_a_0_1_string_till_here[i]+count_1[n]-count_1[i]+count_0[n]-count_0[i]);
}
cout<<ans<<endl;
}
int main() {
int t;
cin>>t;
while(t--)
{
solve();
}
}
Actually, even if there are no restrictions on the characters at all, the problem is still solvable. Instead of thinking about it as “minimize the number of characters you’ll erase,” think about it as “maximize the number of characters you’ll keep.” So the answer is just N minus (longest non-decreasing subsequence.)
Thanks for this idea. I didn’t think about generalizing the approach. This approach for any number of unique characters would be O(nlogn) from what I remember. If we know what the possible characters are, can this be solved in linear time?
I am referring to the third method here where we can use a fenwick tree, which is quite useful when only some fixed known characters are present. The complexity will be more like O(string_size*log2(number_of_distinct_characters)). But if we know beforehand that the number_of_distinct_characters<=M, then the time is only dependent upon n and it can be considered as O(n) by definition.
But in practice, saying O(n) can be a little misleading.
Hey, beginner here!
What exactly does it mean to make a string non-decreasing?
The actual decimal value of subsequence is larger than or equal to the decimal value of original string
Or
The no of ‘1’ > no ‘0’?
}
the above code was my solution for the above question but codchef’s compiler is telling that the answer is wrong can anyone tell me where I am going wrong
Codechef did a live class on unacademy named ’ Master Dynamic Programming - I/II ’ in case you haven’t already attended it. Provides a great intro to the concept.
