Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Longest Common Substring

Problem Statement

Try it yourself

Problem Statement

Given two strings 's1' and 's2', find the length of the longest substring which is common in both the strings.

Example 1:

Input: s1 = "abdca"
       s2 = "cbda"
Output: 2
Explanation: The longest common substring is "bd".

Example 2:

Input: s1 = "passport"
       s2 = "ppsspt"
Output: 3
Explanation: The longest common substring is "ssp".

Constraints:

  • 1 <= s1.length, s2.length <= 1000`
  • s1 and s2 consist of only lowercase English characters.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
G

Gary

· 4 years ago

Why does the bottom-up table seem to have incorrect values for some positions, like dp[2][3], which means the longest common substring between "cb" and "abd", which should be 1 instead of 0 since "b" is the one common substring?

Show 1 reply
L

Lucifer

· 4 years ago

what is the time and space complexity of the top-down solution?

Show 2 replies
G

Gaurav Sisodiya

· 4 years ago

@designgurus - It would be great if you could add some explaination for the space optimal solution and make it more elaborative.

Show 4 replies
Peng Xu

Peng Xu

· 3 years ago

For below test case when s1="passport" and s2 = "ppsspt"

I got result 1 for the longest common substring. Seems the solution might not be correct. could you help to check?

class Solution:
  def findLCSLength(self, s1, s2):
    # TODO: Write your code here

    # index 1 and 2
    def helper(i1, i2, count):
      if i1 == len(s1) or i2 == len(s2):
        return count
      
      if s1[i1] == s2[i2]:
        return helper(i1+1, i2 + 1, count + 1)
      else:
        c1 = helper(i1, i2 +1, 0)
        c2 = helper(i1+1, i2, 0)
        c3 = helper(i1 + 1, i2 + 1, 0)
        return max(c1, c2, c3)

    return helper(0,0, 0)
Show 2 replies

On This Page

Problem Statement

Try it yourself