DP 26. Print Longest Common Subsequence | Dp on Strings

a

In this video, we print the LCS. Please watch DP 25 before watching this.

[hashcodez]

"UNDERSTOOD BHAIYA!!"

Please also add a follow up problem - "HOW TO PRINT ALL LCS IN LEXICOGRAPHICAL ORDER".

[shatanshubodkhe]

Now this is what i was waiting for !
He wasn't drawing any tables till this video and now this series truly looks complete!!!!

[rahatsshowcase]

Now i understand the twist ! In many dp questions i have seen like this that they told to print ! But I was like then how will i do dp? But this concept was in next level! Those who have a very deep understanding of dp only they can do it! US and thanks

[charankumarvaddepally]

The only part I dont understand in striver's lectures is "hey vian" at the start of the video. Rest all as smooth as it can get.

[sameersahu]

Never thought tracing back in the DP matrix was so easy!!Understood....Thank you

[vanamgangireddy]

alternate method just observe last column where value changes

string str="";
for(int i=m;i>0;i--)
{
if(dp[i][n]!=dp[i-1][n]) str=s[i-1]+str;
}
cout<<str<<endl;

[pushkarwaykole]

Very nicely explained, I was not able to find the printing of lcs . Lucky found this video.
Thank you

[rohan]

Awesome explanation Striver, it seems God has sent you as Angel to prepare me to a high paying job!

[anshumaan]

Abhi me 3rd year me hu, mere 2nd year me subject tha ADA(Algorithm and Design Analysis), mujhe yaad hai teacher yhi question krra rha tha, tab mujhe samaj nhi aya tha kuch, kyoki na tab mujhe DP itne acche se aati thi, na hi mujhe yeh pta tha ki yeh dp table kese aayi aur isse backtrack kese kr rhe hai
Lekin ab sab clear ho gya hai, Thank you vro 🙂

[gsampath]

Frankly, Your website is much helpful, then video tutorial.

[AkashSingh-mkod]

Great explanation. Understood it clearly🤩🤩. However, i was curious what if we use dp array itself to store the subsequences. It will eliminate the need of backtracking the dp array and hence will not produce the extra time complexity of O(n+m) in addition to O(n*m). Also this will allow us to use space optimized tabulation solution with max space complexity of O(m)*O(min(n, m)) where O(min(n, m)) is the space complexity to store the subsequence.

[ganishk]

Instead traversing either last row or column may be optimal one right -> **TC: O(min(n1, n2))** but this approach may use **O(n1+n2)** as TC.

[ratmouse]

Understood! By far best explanation I have found.

[raghavmanish]

understood....thanku striver sir/bhaiya

[sahilbadkul]

Understood man, your explanation is so simple to grab any concept.😄

[manumanohar]

For finding all possible pairs
use backtracking and also apply memoization by memoizing i, j, current_lcs(all strings possible upto i, j)

[Hrishu_Indian_boy]

One doubt, how to print all subsequences of maximum length? E.g. abaaa and baabaca has 3 common subsequences of maximum length 4: aaaa, abaa, baaa.

[ranasauravsingh]

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

[googleit]

Done and dusted in revision :)

Nov'14, 2023 04:50 pm

[abhishekmurthy]

Loved your video sir
One alternate method that kind of worked out for me was this, do let me know if this will any edge cases


int count = 1;
String ans = "";
for(int i=0; i<dp.length; i++){
    for(int j=0; j<dp[0].length; j++){
        if(dp[i][j] == count){
          count += 1;
           ans += s1.charAt(i-1);
        }
    }
}
System.out.println(ans);