Longest Duplicate SubString

Posted: 10 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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

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