Last Updated: 10 Mar, 2021

Longest Duplicate SubString

Moderate

Asked in companies

Solve now

Problem statement

You are given a string 'S' and you need to return the length of the longest duplicate substring in the given string. The occurrence of duplicate sub-strings can overlap also.

If there are many longest duplicate sub-string return any of them.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of the test case contains a single string 'S'.

Output format :

For each test case, print a single line containing a single integer denoting the length of the longest possible duplicate substrings.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 50
1 <= length of string <= 200

Time limit: 1 sec.

Solve now

Approaches

01 Approach

The key idea is to find all possible substrings and keep the count of all substrings and return the length longest substring which appears more than once.

Algorithm:

Create an ans variable initial value 0.
Run a loop from i = 0 to len of(string).
Inside this loop run a from j = i to length(string).
Check if the count of substring from i to j appears more than one time. If it appears more than one time then replace the ans by length substring if substring length is greater than ans.
Increase the count of a substring by 1.
In the end return the ans .

Solve now

02 Approach

The key idea is to find the longest common substring using dynamic programming between the same string such that their ending index are not same.

Algorithm:

Create an auxiliary dp matrix of size n*n with default value 0 where n is the length of string.
Run a loop from i=1 to n and inside this loop run another loop from j=1 to n.
If s[i - 1] == s[j - 1] and i != j then dp[i][j]=1+dp[i - 1][j - 1]. Where dp[i][j] denotes longest common substring in s[1..i] and s[1..j] when ith and jth character are included.
The longest possible substring will be the maximum value in dp matrix. Return the maximum value dp auxiliary matrix.

Solve now

03 Approach

The key idea is to check if a duplicate substring of a particular size exists or not.To check if a particular size duplicate substring exists we will use Rabin-Karp algorithm.

Algorithm:

Create ans with initial value 0.
Create two-variable hi = n , li = 1 where n is the length of the string.
Create mid = (hi + li) / 2.Check if any substring of length l contains duplicates.
To check that apply Rabin Karp algorithm on the given string.
It will create hashed value for every substring of size mid. It will compare all strings with the same hash. If any of the strings is found the same it will return true else return false.
If the duplicates of the substring of length mid is found then change li to mid + 1 and ans equal to mid .Else do hi = mid - 1.
In the end return ans .

Solve now