DP 31. Shortest Common Supersequence | DP on Strings 

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 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..........Thanks a ton Striver Bhaiya for this wonderful series.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

Understood :) Prolly the toughest problem so far. Did it on my own in some other way, feeling v v satisfied

at 1:35 you get the idea and solve the problem , striver is GOAT

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 👍😂🔥

Thank you so much striver for wonderful series. Understood every problem present in the series

Understood, thanks. Both of the vides helped a lot to understand string extraction from DP matrix via tabulation :)

Use scs = char + scs, instead of reversing the string.

you are golden! thanks to you(for explaining such complex problems with ease) hearts won't be broken anymore

Understood!!! another LC HARD problem, but your explanation and previous concepts makes it looks so simple!!! AMAZINGGG!!!LOVEDD IT

Understood. You made it simple to understand how to pick uncommon elements into our result string.

How to determine when to use DP table for solving a problem or when to use recursion or memo ??

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.

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

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

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

4:41 : suffice meaning - to be enough for somebody/something 🙂

Great explanation bhaiya!! Understood this concept of printing the shortest supersequence using LCS DP table clearly...Thanks. This was indeed a difficult one..

Bhaiya shayad aapne glti se shortest ki jagah longest likh diya title me

Thank you Understood!!!

7:45 n(AUB)=n(A)+n(B)-n(A^B) 😊

TC -> O(n+m), for traversing the dp[][] table

this guy deserves every follower he got

Please update the notes on websites it is only upto lec 23 , notes are very helpful 👍 bhaiya .... thanks for your hard work keep going

"UNDERSTOOD BHAIYA!!"

Understood ❤

Done on my own🤩🤩thanks striver

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

Understood. Great content striver. Keep it up. Thanks for all your efforts to uplift the community.

Understood! You explained it so well! Thank you so much for making these videos

nice sir..understood.

Thank you sooo much striver , this playlist is just amazing, mind-blowing, just like a woow

Understood 🙏

Understood sir!!!

thanks sir !! cant express my gratitude in word.

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....It took me so long but I solved this without watching video and I'm so happy ....thank you striver you are the best

Thanks a lot sir for this amazing series😇.

Thank you so much STRIVER for these amazing videos!!🙌🙌❤❤

only because of you solution came into my mind before your explanation.

Understood kaka!

understood....thanku striver

21:53 , similar to what we did at end of merge sort

US, the DP on string is still something which is not eas for me to pick up, as I cant see the patterns by myself. but after watching half of the video I was able to code the solution

Great explanation underStand Striver

Just dooper explanation Understood sir!!! ❤️ Thank you sooooooo much for your striving efforts

Wonderful explanation!

Thanks Striver. Understood SCS. How to use the space optimized DP for this problem?

Thank you for the playlist ❤

What about str1=bruteo str2=groot For this I think this is not working if working give wrong ans.

I have a doubt here, what if the common letters are not in right order? Ex: s1=horse, s2 = rose. In this case we will end up with hrorse or rhorse we are taking r twice. Isnt it wrong?

Done and dusted in DP revision :) Though took a lot of time to figure out (~33mins) Nov'17, 2023 06:07 pm

ustaadan de ustaad😍😍

Understood! I can't thank you enough

Unbelievable 😂this time

Amazing Explanation ❤❤

We might have more then one Supersubsequence for one problem and both have same length. like s1= brute s2= groot Result1= bgrooute and Result2 = bgruoote then which one will be prefer.

Understood! Thank you so so SO much as always!!

For those who are Having any difficulty getting proper code : Note** The apporach is in reverse that of what raj bhai did . 🙂 class Solution { public: string shortestCommonSupersequence(string s, string t) { int n= s.size(); int m= t.size(); string super=""; vector dp(n+1, vector (m+1 , 0)); for(int i=n-1; i>=0; i--){ for(int j=m-1; j>=0; j--){ int take=0, nottake=0; if(s[i]==t[j]) take= 1 + dp[i+1][j+1]; else nottake= (max(dp[i+1][j], dp[i][j+1])); dp[i][j]= max(take, nottake); } } cout

understood , Thank you Striver

amazing explanation

*exclaims "I am groot" after solving this question* 💪

Understood sir😄

Thank you so much, Understood.

Understood!! Wonderful explanation!!!

Awesome video . Striver orz 🙏

Great Explanation

Thanks striver❣️

loved the way u explained 💚💚💚💚

Understood.

UNDERSTOOD...!! Thanks striver for the video... :)

understooodddddd!!!!!!!!!!!!!!!

Understood 🎉

Understood 💯💯💯

UNDERSTOOD

What if we have tho print all the supersequence possible then ???

Understood...Completed (31/56)

understood striver

Thank You :)

Thanks

Omg ! Just awesome 👍👍❤

Understood🌻

Its nice to directly use DP table, but it would be great if you can explain the recursive part and see if we can develop using that. I tried doing recursive way but got stuck.

understood

Got it Sir

"Understood"!

Understood, thank you!

Understood...

US striver

i solved this. amazing content striver sir.

Understood

NICE EXPLANATION

Understood 🙂✌️✌️

Understood, sir. Thank you very much.

Undesrtood well and clear

Can this problem is done by using hashset ??