Longest Common Substring

Posted: 14 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given two strings 'STR1' and 'STR2'. You have to find the length of the longest common substring.

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in continuous fashion also.

For example :
If 'STR1' = “abcjklp” and 'STR2' = “acjkp”  then the output will be 3.

Explanation: The longest common substring is “cjk” which is of length 3.
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases.

The first and only line of each test case contains two space-separated strings 'STR1' and 'STR2', respectively.
Output Format:
For each test case, return the length of the longest common substring among the two strings.

Print the output of each test case in a separate line.
Note:
You don't need to print anything, it has been already taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= |STR1|, |STR2| <= 100

Where |STR1| and |STR2|  are the lengths of the string 'STR1' and 'STR2' respectively.

Time limit: 1 sec
Approach 1

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 maximises 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 starting of the two strings.
Try Problem