Interview Bootcamp
Vote

0% completed

​

Longest Common Substring

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:

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lucifer

· 4 years ago

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

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

Khushal Singh

· 17 hours 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