Longest Common Subsequence (2 Strings) – Dynamic Programming & Competing Subproblems

Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems

167705 People Read – 7609 People Liked – You Can Also Like

Code & Problem Statement @ https://b2bswe.co/longest-common-subsequence

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching

Question: You are given 2 strings. Return the length of the longest subsequence that the 2 strings share.

Complexities

n = s1.length()
m = s2.length()

Time: O( nm )

We can upper bound time by the number of subproblems that we are going to solve.

Space: O( nm )

We upper bound space by the number of subproblems we will story answers to. Whether we do (n + 1)(m + 1) or (n)(m) doesn’t matter asymptotically.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

Youtube

Make Beautify

Longest Common Subsequence (2 Strings) – Dynamic Programming & Competing Subproblems