how it tells about the no of element to be deleted
P[w][i - 1] + (j - i + 1) - (P[w][j] - P[w][i - 1]) + (P[w][n] - P[w][j])
How to format my code ?
Wrap your code in backquotes(`), or post a link to your submission.
Please explain wrapping the code in backquotes.
Simply enclose it in backquotes.
I tried it, but it didn’t help. See my last post’s edit history.
Try using three backquotes; such as (triple backquote) (newline) (code) (newline) (triple backquote)
Or add 4 spaces in the beginning to each line
i simple found the largest continuous bunch of 0s and 1s and subtracted it from the total no of 0s and 1s respectively and took the minimum of both
for example
10111000010
this has the longest continuous bunch of 0s as 4
and longest continous bunch of 1s and 3
so the ans would be min of 6-4, 5-3 which is 2
thankyou so much 
In this line,
shows number of w characters in [1,L-1]
shows number of 1-w characters in range [L,R]
shows number of w characters in [R+1, N]
Correct me if wrong !
1
11111111111100001000010000111111111100000
Your Output is 12 but answer should be 7 by removing 2-1 in mid and 5-0 at last
1111111111110000000000001111111111
Oh good, didn’t notice that ; but you should be able to prove the correctness of your solution(which I think it is correct)! Can you?
Please explain with an example.it would be a great help. please
bro please explain your code in detail.please
I think this can be solved in o(n) time complexity.
we want (101) or (010) as our resulted block string.
this can be achieved by -
case 1 :- the string starts with ‘1’
delete all the ‘0’ blocks between first ‘1’ and last ‘1’ except the block having
maximum frequency + all the ‘0’ blocks after the last ‘1’ .
case 2:- the string starts with ‘0’
same as above with (‘1’ replaced with ‘0’) .
here is my code -
#include <bits/stdc++.h>
using namespace std ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int n ;
string str ;
cin>>str ;
n = str.length() ;
int num_1,num_2,num_3,num_4 ;
int cnt_0=0, cnt_1=0, cnt_temp=1 ;
vector<int> cnt0,cnt1,cnt ;
int start ;
str[0]=='0'?start=0:start=1 ;
string str1 ;
if(n<=3)
{
cout<<"0\n" ;
continue ;
}
for(int i=0;i<n;i++)
{
if(i>0)
{
if(str[i-1]!=str[i])
{
str1.push_back(str[i]) ;
cnt0.push_back(cnt_0) ;
cnt1.push_back(cnt_1) ;
cnt.push_back(cnt_temp) ;
cnt_0 = cnt_1 = 0 ;
cnt_temp = 1 ;
if(str[i]=='0')
cnt_0 = 1 ;
else
cnt_1 = 1 ;
}
else
{
if(str[i]=='0')
cnt_0++ ;
else
cnt_1++ ;
cnt_temp++ ;
}
}
else
{
str1.push_back(str[i]) ;
if(str[i]=='0')cnt_0++ ;
else cnt_1++ ;
}
}
cnt.push_back(cnt_temp) ;
if(str[n-1]=='1')
cnt1.push_back(cnt_1) ;
else
cnt0.push_back(cnt_0) ;
n = str1.length() ;
if(start == 1)
{
int temp = 0, maxi=0, len ;
for(int i=1;i<n-2;i++)
{
if(str1[i]=='0')
{
maxi = max(maxi,cnt[i]) ;
temp+=cnt[i] ;
}
}
if(str1[n-2]=='1')
temp= temp - maxi + cnt[n-1] ;
else
{
temp+=cnt[n-2] ;
maxi = max(maxi,cnt[n-2]) ;
temp-=maxi ;
}
num_1 = temp ;
cout<<num_1<<"\n" ;
}
else
{
int temp = 0, maxi=0, len ;
for(int i=1;i<n-2;i++)
{
if(str1[i]=='1')
{
maxi = max(maxi,cnt[i]) ;
temp+=cnt[i] ;
}
}
if(str1[n-2]=='0')
temp= temp - maxi + cnt[n-1] ;
else
{
temp+=cnt[n-2] ;
maxi = max(maxi,cnt[n-2]) ;
temp-=maxi ;
}
num_2 = temp ;
cout<<num_2<<"\n";
}
}
return 0 ;
}
but I am getting W.A can anyone explain why??
Cannot we do it using simple brute force approach??
Please help as this problem seems to be quite straight forward.
Thanks.
hey. I did exactly like this but it will give WA,
example - 11110110000100
as per our code, answer will be 3(remove 2 ‘0’ blocks or ‘1’ blocks), but the answer should be 2(remove first 0 and last 1)
11111111111100001000010000111111111100000
Your output is 12 but correct output is 7
My solution: CodeChef: Practical coding for everyone
Where does my code fail?
Please let me know if someone finds out.