Last Updated: 14 Mar, 2021

# Longest Common Substring

Moderate

## Problem statement

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