Grokking Dynamic Programming Interview/

...

/

Solving the Longest Common Substring Problem

Solving the Longest Common Substring Problem

Let's solve the Longest Common Substring problem using Dynamic Programming.

We'll cover the following...

Statement

Given two strings s1 and s2, you have to find the length of the Longest Common Substring (LCS) in both these strings.

Let’s say we have two strings, “helloworld” and “yelloword”, there are multiple common substrings, such as “llo”, “ello”, “ellowor”, “low”, and “d”. The longest common substring is “ellowor”, with length 7.

Constraints:

  • 1≤1 \leq s1.length , s2.length ≤\leq 400400

  • s1 and s2 consist of only lowercase English characters.

  • Spaces are not allowed.

Examples

No.

s1

s2

Length of LCS

1

helloworld

helloold

5

2

educativeexplore

educativeexpress

12

3

educativeisfun

algorithmsarefun

3

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > Main.java
import java.util.*;

public class Main{

    public static int lcsLength (String input1, String input2) {

        // Write Your Code Here

        return 0;

    }

}
Longest Common Substring

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 dynamic programming.

Naive approach

Let’s look at this problem on a smaller scale. We are comparing each character one by one with the other string. There can be three possibilities for the ith^{th} character of s1 and the jth^{th} character of s2:

  1. If both characters match, these could be part of a common substring, meaning we should count this character towards the length of the longest common substring.

  2. ith^{th}character of s1 might match with (j+1)th^{th}character of s2.

  3. jth ...

Access this course and 1400+ top-rated courses and projects.