Longest Common Substring

Hard
0/120
16 upvotes
Asked in companies
DunzoCommvault

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first and only line of each test case contains two space-separated strings str1 and str2, respectively.

Output Format: 
For each test case, print the length of the longest common substring among the two strings.

Print the output of each test case in a separate line.
Constraints: 
1 <= T <= 100
1 <= |str1|, |str2| <= 100

where ‘T’ is the number of test cases and |str| is the length of the string str.
Sample Input 1:
2
abcjklp acjkp
wasdijkl wsdjkl
Sample Output 1:
3
3
Sample Input 2:
2
abcy acby
tyfg cvbnuty
Sample Output 2:
1
2

Explanation: The longest common substrings in first test case are “a”, "b", "c", “y” all having length 1.

Hint

Can you think of checking if substrings of the first string also exist in the second string?

Approaches (4)
Brute-Force

The basic idea is to start slicing the first string into the substring and match those substrings in the second string.

 

  • Take a variable “ans” initialized to 0, which keeps track of the longest common substring among the two strings.
  • Run a loop to traverse the first string “str1”. In this way,we can get the starting index of the substrings.
  • Run another loop to traverse the second string “str2” to match characters of string “str2”.
  • Take a variable, say ‘k’ initialized to 0 that will act as an iterator to match the strings.
  • Now start matching characters of strings “str1” and “str2” i.e from index [i + k] and index [j + k] where ‘i’ is the starting index of the substring of first string and ‘j’ is the starting index of the substring of the second string.
  • If they match, increment the value of ‘k’ and check for next characters of both strings and update the value of “ans” variable.
  • If they do not match, change the value of ‘k’ to zero and move a step ahead in the second string.
Time Complexity

O((N*M*min(N,M)), where ‘N’ and ‘M’ are the lengths of the two strings.

 

Since we are traversing both strings of size ‘N’ and ‘M’ and matching the substrings of both the strings has O(min(N,M)) time complexity. So overall time complexity will be O((N*M*min(N,M)).

Space Complexity

O(1).

 

Constant extra space required.

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