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
. . . .
Khushal Singh

Khushal Singh

· a month ago

Simple Solution

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

def one(s1, s2):
  n1 = len(s1)
  n2 = len(s2)
  return rec(0, 0, 0, s1, s2, n1, n2)

def rec(ind1, ind2, curr, s1, s2, n1, n2):
  if ind1 == n1 or ind2 == n2:
    return curr

  # Match
  if s1[ind1] == s2[ind2]:
    return rec(ind1 + 1 , ind2 + 1, curr + 1, s1, s2, n1, n2)
  
  # NOT Match 
  case1 = rec(ind1 + 1 , ind2, 0, s1, s2, n1, n2)
  case2 = rec(ind1 , ind2 + 1, 0,  s1, s2, n1, n2)
  return max(curr, case1, case2)

Explanation

  • Take ind1 and ind2 to point out current position for which we are comparing.
  • There can be two cases only
    • Character match
      • increment the current count (stored in curr variable)
      • In t
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
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
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
L

Lucifer

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