I used substring function to get two substrings and got the subscore for each combination and calculated the maxScore of all the subscores. The explained algorithm is super intuitive .Thank you
Sir As you know some of the youtubers ask us to explain the brute force then better then optimal solution to interviewer ,so we should write seperate code for all of these? Or just we can explain orally the brute force and better approach and then go for the optimal approach for coding with explanation just like you do in your videos. Because in some topics like recursion backtracking graphs dp etc.. brute force and better approach are cumbersome to code than optimal approach.
🎉no need to take array just make 1 loop for finding out total number of one's Then just make one initialisation for sum of zeros in left and in loop increment it and just make checks if it's 1 then reduce the sum of 1 by 1 and simply take max of sum of sum of 0 and sum of 1
because split should have 1 element on right side :) therefore need to stop at 2nd last index. I think you can take your examples and do some dry runs on my code. If you still have confusion pls post here.
// Approach 2 ->> 2 Iterations... // TC= O(2*N) class Solution{ public: int maxScore(string str) { int n= str.length(); vector rightOne(n,0); rightOne[n-1]= (str[n-1]- '0'); for(int i=n-2;i>=0; i--) { rightOne[i]= rightOne[i+1] + (str[i]- '0'); } int maxi= 0, cnt= 0; if(str[0]== '0') cnt= 1; for(int i=1; i Using seperate vec for cnt of zeroes on left side and ones on right side // TC= O(3*N) /* class Solution { public: int maxScore(string str) { int n= str.length(); vector leftZeroes(n,0); if(str[0]== '0') { leftZeroes[0]= 1; } for(int i=1;i=0; i--) { rightOnes[i]= rightOnes[i+1] + (str[i]-'0'); } int maxi= 0; for(int i=1; i
I used substring function to get two substrings and got the subscore for each combination and calculated the maxScore of all the subscores. The explained algorithm is super intuitive .Thank you
we should avoid creating substrings as it costs a lot on runtime
Yes I got it and searched for an optimal solution. Thank you sir .
Sir
As you know some of the youtubers ask us to explain the brute force then better then optimal solution to interviewer ,so we should write seperate code for all of these?
Or just we can explain orally the brute force and better approach and then go for the optimal approach for coding with explanation just like you do in your videos.
Because in some topics like recursion backtracking graphs dp etc.. brute force and better approach are cumbersome to code than optimal approach.
No. the burteforce and suboptimal solutions will soon be genrally skiped in a few minutes :)
I maintained prefix sum array from left and right for 0 and 1
nice
🎉no need to take array just make 1 loop for finding out total number of one's
Then just make one initialisation for sum of zeros in left and in loop increment it and just make checks if it's 1 then reduce the sum of 1 by 1 and simply take max of sum of sum of 0 and sum of 1
@@Chetanmarathe-j6f yeah I realised later on
Super...I tried to use two arrays one count and zero count and traverse both
nice
Best explanation
🙏🏼
why should we have s.size() for counting one's and s.size()-1 to check 0's
because split should have 1 element on right side :) therefore need to stop at 2nd last index.
I think you can take your examples and do some dry runs on my code.
If you still have confusion pls post here.
@ got it thanks
I was just solving this question 😮😮
nice
// Approach 2 ->> 2 Iterations...
// TC= O(2*N)
class Solution{
public:
int maxScore(string str) {
int n= str.length();
vector rightOne(n,0);
rightOne[n-1]= (str[n-1]- '0');
for(int i=n-2;i>=0; i--)
{
rightOne[i]= rightOne[i+1] + (str[i]- '0');
}
int maxi= 0, cnt= 0;
if(str[0]== '0') cnt= 1;
for(int i=1; i Using seperate vec for cnt of zeroes on left side and ones on right side
// TC= O(3*N)
/*
class Solution {
public:
int maxScore(string str) {
int n= str.length();
vector leftZeroes(n,0);
if(str[0]== '0')
{
leftZeroes[0]= 1;
}
for(int i=1;i=0; i--)
{
rightOnes[i]= rightOnes[i+1] + (str[i]-'0');
}
int maxi= 0;
for(int i=1; i