guys sorry for the bad formating yesterday
Question 1=>
so you are given an array of integeres, you need to count the maximum number of partiotions that you can do, here partition means dividing the array into 2 parts such that the sum of both parts are equal. In addition to this you can do this operation once, change a number to 0
test case 1=> 6
-1 5 0 0 5 0
answer is 3, here we change -1 to 0
Question 2 => you are given a string of lower case english alphabets, you need to find the numbebr of palindromic triplets, A palindromic triplets is as such, suppose you have 3 non overlapping substring S1,s2,s3 then this triplet is a plaindromic triplet if all the individual substrings are palindromes and non overlapping. We need to find the number of such triplets
test case 1=> 4
abaa
answer is 5
Do you have the constraints for both problems?
expected time complexity for first one is o(n) ans second is o(n^2)
Well, second one's constraint is too harsh :(
any hints how to solve first q in o(n)
small correction: Instead of
here we change -1 to 0
, it should behere we change -1 to 5
Well, it's mentioned in the problem that you can only change a number to 0.
Oh, didn't notice. Then shouldn't answer be 2? i.e. say two partitions: [0,5] and [0,0,5,0] having equal sums of 5
Array: 0 5 0 0 5 0
0 5 | 0 0 5 0
0 5 0 | 0 5 0
0 5 0 0 | 5 0
can a problem be done like this .. for every number store (rightsum-leftsum) in a map ..
for given case : 11 1 1 1 -9 -9 would be the corresponding (rightsum-leftsum)..
now check for each number .. if we change -1 to 0.. check how many times we have 1 in the map .. similarly check for -5 for element 5
Correct, and if you do leftsum — rightsum, you'll have to check the same number in the map, not the negative of the number. Am I correct?
Right
can you please elaborate more on that, like how 2 times -9 is there? and give some pseudo code....Pls
i think this should work
I don't think so , try for
2 2 0 0 5 0 0 2 2
yes you are right .. now i was thinking to check for both -it and +it in the map .. and adding both the maxs.. is it still wrong ?
for first question compute prefix sum and store the frequency of element in map now start iterating from left to right if you making ith element zero count frequency of element (sum+pref[i])/2 on left side and right side and take max of the sum.
i guess itll work
Would you please share the code for the same....
for second question first compute matrix is_palindrome[i][j] (0 and 1) now find number of palindrome from i to j using dp. dp[i][j]=dp[i+1][j]+dp[i][j-1]+is_palindrome[i][j]-dp[i+1][j-1] (takes o(n^2)) now compute number of triplet from (0,i),(i+1,j-1),(j+1,n) using two nested loop and take the sum of the product . I think this will work here is code for dp.
wont this approach count some triplets multiple times. Can you please prove that this works ?
yeah, I guess you are right!
2nd question is DP we choose a substring if it is palindrome and 3 palindromes are required so we decrease the required count by one and will try to find the next remaining palindromes we can precompute the next indices for an index that will form a palindrome or we can check on go that will be overall worst worst-case O(n^2) here is the code:-
I think this will work if any correction needed pls do let me know it would be grateful to know other approaches...
the second loop causes duplicate counting, rather remove the loop and replace it with ans+=counttriplets(i+1,rem,s);
whats the approach for second one?
i used a sparse table to keep track of all palindromic substring so using that you can know if the substring i-j is palindrom in 0(1), now i need to count the number of palindromic substring which end before i and start after j then multiply them
in second step, you are going to multiply nofPalins(0, i) * nofPalins(i+1, j) * nofPalins(j+1, n) right?
Wont this count some triplets multiple times?
nah
It will count multiple time ig for some strings eg ababab no of palindrome from 0 to 1 is 2 and from 0 to 2 is 4 but when you multiply contribution of 0 to 1 occurred again
I have pics for these questions. Drive Link
thanks fren
For question 2 ig the following code should work (comments to explain what i did) Let me know if there are any testcases on which my code fails.
I think the following should work for the 1st one -
This should work for q2