Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 14 Mar, 2021

Longest Common Substring

Moderate
Asked in companies
Wells FargoShareChatAdobe

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

Approaches

01 Approach

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.