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
. . . .
A

Anonymous

· 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 1 reply
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 5 years ago

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

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself