How to solve?
Need Help! For which test case this will fail?
import java.util.*;
public class Test{
public static void main (String args[]) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
in.nextLine();
for(int tc =0 ;tc<t;tc++){
int ans =0 ;
String s = in.nextLine();
int nn= s.length();
int one=0;
int zero =0 ;
//creating new string by squeezing original string, if s = 100010011110 the solo = 101010
String solo = "";
for(int i=1 ;i<nn;i++){
if(s.charAt(i)=='1' && s.charAt(i-1)=='0')
solo+=1 ;
if(s.charAt(i)=='0' && s.charAt(i-1)=='1') solo+=0 ;
}
solo = s.charAt(0)+solo ;
//counting number of zeros and ones
int n = solo.length();
for(int i=0 ;i<n;i++)
if(solo.charAt(i)=='1')
one++;
zero = n - one ;
ans = Math.min(one - 1 ,zero -1);
System.out.println(Math.max(0,ans));
}
}
}
111100010001111 ??
What output?
1
String–>111100000111
11011000
and
011011000
What output?
Is there DP solution? Can we memoize the recursive solution somehow?
i calculated number of 0 and 1
then i calculated length of longest continuous sequence of 1 and 0 respectively
and answer = min(no. of 0 - maximum continuous length of 0s , no. of 1 - maximum continuous length of 1s)
e.g suppose string is 1011100001011101
no. of 0=7
no. of 1=9
max. no. of continuous 0 =4
max. no. of continuous 1=3
so answer=min(7-4,9,3)=3
which is given in test case also
but my code is giving WA any improvement/changes ?
1 for both
String1 (11011000)->1111000
String2 (011011000)–> 01111000
I also did the same and its the wrong approach I think!
It wail fail for the test cases i mentioned above!
i have done the same thing but WA
Here is my code. Did the same thing but got WA.
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int count0 = 0;
int count1 = 0;
vector<char>p;
int k=0;
for(int i=0 ; i<s.length();i++){
p.push_back(s[i]);
while(s[i]==s[i+1]) {
i++;
}
}
for (int j = 0; j < p.size(); ++j) {
if(p[j]=='0') {
count0++;
}
else
count1++;
}
if(min(count1,count0)-1 == -1){
cout<<"0"<<endl;
}
else
cout<<min(count1,count0)-1<<endl;
}
return 0;
}
11011000 - output: 1 i.e removing index 2 (starting from 0)
011011000- output: 1 i.e removing index 3
in both cases 1 is the minimum no of character to delete so that both 1010 & 0101 subsequences are avoided.
Well I used DP to calculate 6 counts for every run of either 0 or 1, the counts respectively represented the min deletion for a sequence of 0s, 1s, 0s and then 1s, 1s and then 0s, 0s then 1s then 0s and 1s then 0s then 1s; the updations are easy.
My Submission
The final string can either be solely of 0s, solely of 1s, of 0s and then 1s and so on; those are the 6 possibilities
Your approach fails for case 1001001111.
Could anyone please point out the test case for which this will fail-
`#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int count = 0;
int n = s.length();
int f = 0, j = 0, aa[10000] = { 0 }, bb[10000] = { 0 };
for (int i = 0; i < n; i++) {
if (s[i] == '0' && f == 0) {
count++;
f = 1;
aa[j]++;
}
else if (s[i] == '1') {
j++;
f = 0;
}
else {
aa[j]++;
count++;
}
}
if (count == 1 || count == 0 || j == 0) {
count = 0;
}
else if (s[0] == '0' && s[n - 1] == '0') {
sort(aa + 1, aa + j);
count = min(count - aa[0] - aa[j], count - aa[j - 1]);
}
else {
sort(aa, aa + 10000);
count = count - aa[9999];
}
j = 0;
int count1 = 0;
f = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1' && f == 0) {
count1++;
f = 1;
bb[j]++;
}
else if (s[i] == '0') {
j++;
f = 0;
}
else {
count1++;
bb[j]++;
}
}
if (count1 == 1 || count1 == 0 || j == 0) {
count1 = 0;
}
else if (s[0] == '1' && s[n - 1] == '1') {
sort(bb + 1, bb + j);
count1 = min(count1 - bb[0] - bb[j], count1 - bb[j - 1]);
}
else {
sort(bb, bb + 10000);
count1 = count1 - bb[9999];
}
if (count < count1) {
cout << count << endl;
}
else {
cout << count1 << endl;
}
}
}`
Bro can you tell where you learned and practiced DP.
Can’t understand that much from the code, really weak in CPP and DP. My approach was to keep a stack tracking the current state of elements taken, until that is invalid (1010 or 0101) in which case I return INT_MAX, if my state is 010 and a 0 comes, I keep it same as 010 and if it was 101 and a 1 comes I keep it same as 101.
Then I was recursively calling the function with res = MIN(select current element, not select current element) and I was incrementing a deletion variable keeping track of number of deletions. If I exceed the length of array, I return deletions.
Can you tell me if this approach is totally insane or maybe it can be used?
Can someone help me identify where I am going wrong?
Can’t it be solved using this approach?
I check if there is a lcs of given string with 0101 or 1010.
If length of lcs <=3, then no deletions in s are required else delete any character i (0<i<n) and recursively solve for it and take the minimum out of it like the loop inside recursive solution in rod-cutting problem;
int delete(string s, int i, int n){
if (lcs(s,“0101”)<=3 && lcs(s,“1010”) <=3)
return 0;
else
int i,mi=999999;
for(i=0;i<n;i++){
string p=s;
erase(i,1); // The string s is copied to p and ith character is erased.
mi=min(mi, 1+del( p, i, n-1 ));
}
}
I think it might work, but you would need to memoize, also you can directly work on runs(blocks of same character).