Longest Common Subsequence Leetcode Solution

Longest Common Subsequence Leetcode Problem :

Given two strings text1 and text2, return the length of their longest common subsequenceIf there is no common subsequence, return 0. subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
  • For example, “ace” is a subsequence of “abcde”.
common subsequence of two strings is a subsequence that is common to both strings.
jump game leetcode

Longest Common Subsequence Leetcode Solution :

Constraints :

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.

Example 1:

  • Input: text1 = “abc”, text2 = “abc”
  • Output: 3
  • Explanation: The longest common subsequence is “abc” and its length is 3.

Intuition :

The problem requires finding the length of the longest common subsequence (LCS) between two given strings, text1 and text2. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

To solve this problem, we can use dynamic programming. We’ll create a 2D matrix, dp, where dp[i][j] represents the length of the LCS between the first i characters of text1 and the first j characters of text2.

Approach :

  1. Initialize a 2D matrix, dp, with dimensions (m + 1) x (n + 1) (where m is the length of text1 and n is the length of text2). Initialize all values in dp to 0. 
  2. Iterate through text1 from index 1 to m (both inclusive), and for each character text1[i – 1]:
  3. Iterate through text2 from index 1 to n (both inclusive), and for each character text2[j – 1]: 
  4. If text1[i – 1] is equal to text2[j – 1], update dp[i][j] as dp[i – 1][j – 1] + 1. This means the current characters match, so the LCS length increases by 1. 
  5. Otherwise, take the maximum of dp[i – 1][j] (the LCS length without considering text1[i – 1]) and dp[i][j – 1] (the LCS length without considering text2[j – 1]), and assign it to dp[i][j]. This handles the case when the current characters don’t match, so we need to consider the LCS length without one of the characters. 
  6. Finally, return dp[m][n], which represents the length of the LCS between text1 and text2.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription