Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview

Longest Common Subsequence

Explore how to solve the longest common subsequence problem using dynamic programming. Understand both the naive recursive method and optimized top-down and bottom-up approaches, improving time complexity from exponential to polynomial and reducing space requirements. Gain techniques to efficiently implement and optimize dynamic programming solutions for coding interviews.

We'll cover the following...

Statement

Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.

A subsequence is a string formed by removing some characters from the original string, while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.

If there is no common subsequence, then return 0.

Let’s say you have the following two strings:

  • “cloud”
  • “found”

The longest common subsequence between these two strings is “oud”, which has a length of 33.

Constraints:

  • 1≤1 \leq str1.length ≤2.5×103\leq 2.5 \times 10^3
  • 1≤1 \leq str2.length ≤2.5×103\leq 2.5 \times 10^3
  • str1 and str2 contain only lowercase English characters.

Examples

No.

str1

str2

length

1

"bald"

"bad"

3

2

"nocturnal"

"nick"

2

3

"card"

"tissue"

0

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Main.java
import java.util.*;



public class Main{

    public static int longestCommonSubsequence(String str1, String str2) {

        // Write your code here



        // your code will replace the placeholder return statement below

        return -1;

    }

}
Longest Common Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to compare the characters of both strings based on the following rules:

  • If the current characters of both ...

Ask