DP 31. Shortest Common Supersequence | DP on Strings
Вставка
- Опубліковано 5 бер 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3vEYKce
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Longest Common Supersequence, please watch LCS video before solving this problem.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
A lot of String DP problems simply revolve around LCS, Edit Distance. This problem as well is a pretty good follow-up of LCS where one would build up finding the LCS & then skip the Characters in LCS & pick the remaining ones from both strings.
Thanks Striver for whole DP playlist, I learned alot from this and I did this problem on my own, just because of you. A big THANKS!
Almost did it Myself. Really helpful playlist cuz this is the closest I have gotten to solving a hard question myself
Thank you so much striver for wonderful series. Understood every problem present in the series
Understood!!! another LC HARD problem, but your explanation and previous concepts makes it looks so simple!!! AMAZINGGG!!!LOVEDD IT
Understood. Great content striver. Keep it up. Thanks for all your efforts to uplift the community.
Understood, thanks. Both of the vides helped a lot to understand string extraction from DP matrix via tabulation :)
thank you so much i can,t even imagine i am solving hard dp problems of leetcode so easily so much understandable better than any paid course which i took of coding ninjas and coding blocks
Understood! You explained it so well! Thank you so much for making these videos
you are golden! thanks to you(for explaining such complex problems with ease) hearts won't be broken anymore
UNDERSTOOD..........Thanks a ton Striver Bhaiya for this wonderful series.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thank you so much STRIVER for these amazing videos!!🙌🙌❤❤
Understood. You made it simple to understand how to pick uncommon elements into our result string.
Thank you sooo much striver , this playlist is just amazing, mind-blowing, just like a woow
Bhai aaj ka weekly kidhar hai 😂 I was waiting ki ab aayega ab aayega aur tumne DP ki video daal di, bdhiya compensate kr diya 👍😂🔥
Understood! Thank you so so SO much as always!!
Understood :)
Prolly the toughest problem so far. Did it on my own in some other way, feeling v v satisfied
Can you please tell your approach??
chal jutha
@@rahulbrave1126 abe XD
Thank you for the playlist ❤
UNDERSTOOD...!!
Thanks striver for the video... :)
thanks sir !! cant express my gratitude in word.
Just dooper explanation
Understood sir!!! ❤️
Thank you sooooooo much for your striving efforts
Wonderful explanation!
Thank you
Understood!!!
Understood....It took me so long but I solved this without watching video and I'm so happy ....thank you striver you are the best
Great explanation bhaiya!! Understood this concept of printing the shortest supersequence using LCS DP table clearly...Thanks. This was indeed a difficult one..
loved the way u explained 💚💚💚💚
Understood! I can't thank you enough
Amazing Explanation ❤❤
Understood!! Wonderful explanation!!!
Thank you so much, Understood.
Great explanation underStand Striver
Instead of using LCS, i tried to directly fill in the DP for Shortest Common Superseq, where dp[i][j] = SCS of strings a (from 0 till index i) and b (from 0 till index j)
Code:
#include
string shortestSupersequence(string a, string b) {
// Write your code here.
int n = a.length(), m = b.length();
vector dp(n, vector(m, ""));
string temp = "";
int flag=0;
for (int i = 0; i < m; i++)
{
temp+=b[i];
dp[0][i]=temp;
if(!flag)
{
if(a[0]==b[i]) flag=1;
else dp[0][i]+=a[0];
}
}
temp="";
flag=0;
for (int i = 0; i < n; i++)
{
temp+=a[i];
dp[i][0]=temp;
if(!flag)
{
if(a[i]==b[0]) flag=1;
else dp[i][0]+=b[0];
}
}
for(int i=1;i
Understood, sir. Thank you very much.
understood , Thank you Striver
amazing explanation
Great Explanation
Amazing explanation! You have made DP really solvable, thanks a lot Striver!
While solving though, when memo[i - 1][j] == memo[i][j - 1], I appended str1.charAt(i - 1) and then decremented i and j counters. This yielded wrong output in a test case. To fix that I had to instead compare the characters at those indices. Instead of this condition, I wrote if(str1.charAt(i - 1) == str2.charAt(j - 1) { sb.append(str1.charAt(i - 1); i--; j--; } and it worked just fine. Sounds like the same thing to me but the previous condition was not working I don't know why. Any explanation for this would be deeply appreciated, guys.
TC -> O(n+m), for traversing the dp[][] table
Use scs = char + scs, instead of reversing the string.
Not All Heroes Wear Capes 🦸
i was living under a rock for so long.
it will increase the time complexity for inserting a new character at the beginning of any string will take O(len(str)) Time and we have to do it for let say N times , then it will give us TLE .
@@anumoynandy5811 Good point! I never thought about that!
@@anumoynandy5811 inserting a character in beginning of string is just O(1). And indeed appending it in end of string is o(len(str)).
this guy deserves every follower he got
Awesome video . Striver orz 🙏
Understood ❤
Understood sir!!!
Understood, thank you!
only because of you solution came into my mind before your explanation.
Understood sir ! 🙏🙏
4:41 : suffice meaning - to be enough for somebody/something 🙂
at 1:35 you get the idea and solve the problem , striver is GOAT
Understood sir!
Omg ! Just awesome 👍👍❤
understood. thanks.
i solved this. amazing content striver sir.
Understood Sir thank you very much
understood!!
nice sir..understood.
Thanks striver❣️
we can also find ans by:
iterating over LCS and adding all those characters of stg1 and stg2 that lies before i th character of LCS....because LCS already contains common characters we only need to add those extra characters of stg1 and stg2 to our LCS in same order to conver it into our ANS
//LCS is logest common subsequence string which can be find using DP lec 26
int i=0;
int j=0;
string ans="";
for(int k=0 ; k < LCS.size() ; k++ ) {
while(stg1[i]!=LCS[k])
ans+=stg1[i++]
while(stg2[j]!=LCS[k])
ans+=stg2[j++];
ans+=LCS[k];
i++;
j++;
}
while(i
wrong. giving rte
NICE EXPLANATION
Understood sir😄
Done and dusted in DP revision :)
Though took a lot of time to figure out (~33mins)
Nov'17, 2023 06:07 pm
How to determine when to use DP table for solving a problem or when to use recursion or memo ??
Instead of revolving around memo or recursion try to understand the concept behind the answer, Why this dp array looks like, why this dp[1][2] contains 2 and what does it means. As you will understand the meaning, first try to write the code if possible through recursion or memo, otherwise try to write by your own logic (that you understood why you have created the dp matrix).
understood :)❤
Understood 💯💯💯
Bhaiya shayad aapne glti se shortest ki jagah longest likh diya title me
Understand!
Thank You :)
Hi striver thanks for the detailed explanation,
I have one question if there are 2 longest common subsequence then what should we do in that case?
Like
Str1 = horse
Str2 = ros
Then there are 2 lcs rs and os
Then the supersequence min steps would be 1 > horose but by the formulae it would be 2 steps Horrose
it will be horse itself i think
@@ankitpatil2979 with the formula also the required minimum steps is 1 only, please recheck your calculations
Understood!
Wah bhaiya! Ekdum mast ❤
Thanks
UNDERSTOOD ++👌👌😍😍❤❤
Done on my own🤩🤩thanks striver
whats the Time complexity?
@@anukulsahu O(N*M) where n = size of 1st string and m = size of 2nd same as time complexity of LCS code
ustaadan de ustaad😍😍
understood sir❤️🙏
Instead of Doing Reversal of string....We can also make a dummy string of length (n + m - lcs( s, t ) ) and maintain index to the last of the dummy string and whenever we need that charracter we just update over dummy string and reduce the index..... We can do this na ? @STRIVER #UNDERSTOOD
Yes just like we did in lcd
@@takeUforward Yes like we printed LCS...Thanks
@@takeUforward or we can do like
ans = s[i-1] + ans
Instead of ans+= s[i-1]
@@amankrsingh that operation is costly 😅
21:53 , similar to what we did at end of merge sort
Understood.
Understood 🔥🔥
understooodddddd!!!!!!!!!!!!!!!
understood
Thanks Striver. Understood SCS.
How to use the space optimized DP for this problem?
I saw your comments in almost all videos of this playlist.
Are you in 4th Year?
@@parthsalat Hi Parth. No I am learning DP just like you.
Understood🔥🔥
Understood ❤️❤️🔥🔥
Understood ♥️🌿
Thanks Striver Got It : )
Understood !! 🔥
Understood 🙏
Understood!!🤩
Understood...
Please update the notes on websites it is only upto lec 23 , notes are very helpful 👍 bhaiya .... thanks for your hard work keep going
Coming Soon, Anshuman writes it, I don't wanna give it to other people, as the quality matters, so it will come up soon!
Hi, Anshuman here. Further notes are uploaded. I will complete the remaining ones as soon as possible.
@@anshumansharma4580 uploaded where, here the note's link does not have them, can u please share..
I have a cross question regarding this question that if we want to find smallest resultant string of S1 and S2 strings such that resultant string contains both S1 and S2 as a substring. Smallest resultant string means just returning length of that string. Btw this question came in coding ninja weekly contest 128 which held on 30/05/2024 and that is the 2 question of the contest and I was stuck on this question for next 2 hours in whole contest.
Understood Sir!
Understood
Undesrtood well and clear
Understood!!Can we use the same approach to print as we used in printing LCS...i tried that and it is not working
understood ❤
Unbelievable 😂this time
Understood 🙂✌️✌️
Understood🌻
UNDERSTOOD