Longest Common Substring

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
221 upvotes
Asked in companies
InformaticaWells FargoShareChat

Problem statement

You are given two strings, 'str1' and 'str2'. You have to find the length of the longest common substring.


A substring is a continuous segment of a string. For example, "bcd" is a substring of "abcd", while "acd" or "cda" are not.


Example: 
Input: ‘str1’ = “abcjklp” , ‘str2’ = “acjkp”.

Output: 3

Explanation:  The longest common substring between ‘str1’ and ‘str2’ is “cjk”, of length 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The First line of the test case contains the string ‘str1’.

The Second line contains the string ‘str2’.
Output format: 
Return an integer representing the length of the longest common substring.
Note: 
You don’t need to print anything. Just implement the given function.
Sample Input 1:
wasdijkl
wsdjkl
Sample Output 1:
 3
Explanation Of Sample Input 1 :
 The longest common substring is “jkl”, of length 3.
Sample Input 2:
tyfg
cvbnuty
Sample Output 2:
2
Explanation Of Sample Input 2 :
The longest common substring is “ty”, of length 2.
Expected time complexity:
The expected time complexity is O(n*m),
Where ‘n’ and ‘m’ are the lengths of ‘st1’ and ‘str2’ respectively.
Constraints:
1 <= str1.length <= 1000
1 <= str2.length <= 1000
Hint

Can you think of using recursion for this problem of comparing the strings?

Approaches (3)
Recursion

The basic idea is to recursively try and match characters from ‘str1’ to characters of ‘str2’ and vice versa also.

 

The steps are as follows:

 

  • Create a ‘count’ variable initialized to 0 to get the length of the longest common substring.
  • Try to match the last characters of both strings. Let ‘i’ be the last index for ‘str1’ and ‘j’ be the last index of ‘str2’, so match ‘str1’[i] and ‘str2’[j].
  • If they match, increment ‘count’ by 1 and try to match the preceding characters.
  • If they do not match, make a recursive call to compare ‘str1’[i -1] with ‘str2’[j] and compare ‘str1’[i] with ‘str2’[j -1], and we should choose the option which maximizes our answer i.e. return max(“previous ‘count’”, ‘count’ obtained by matching ‘str1’[i-1] with ‘str2’[j] and ‘count’ obtained by matching 'str1’[i-1] with ‘str2’[j]).
  • Keep repeating these steps until we reach the start of the two strings.
Time Complexity

O(2 ^ (n + m)), Where ‘n’ and ‘m’ is the length of ‘str1’ and ‘str2’, respectively.

 

We are using a recursive function to find the length of LCS where we are comparing each substring of the first string with the second string. 

 

Hence the overall time complexity will be O(2 ^ (n + m)).

Space Complexity

O(max(n , m)), Where ‘n’ and ‘m’ is the length of ‘str1’ and ‘str2’, respectively.

 

We are using a recursive function to find the length of LCS. In the worst case, the call stack may have max(n, m) states.

 

Hence the overall space complexity will be O(max(n, m)).

Code Solution
(100% EXP penalty)
Longest Common Substring
Full screen
Console