Problem

Submissions

Hints & solutions

Discuss

Longest Duplicate SubString

Moderate

0/80

Average time to solve is 30m

5 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1

2
aaaab
abcde

Sample Output 1:

3
0

Explanation of the Sample Input 1:

In the first case, 'aaa' is the longest substring which has two occurrences, the first one starting at index '1' and the second one starting at index '2'(0 - based indexing).

In the second case, there is no substring that appears more than once. Thus answer is 0.

Sample Input 2

2
abcdea
aabbccaa

Sample Output 2

1
2

Hint 1

Hint 2

Hint 3

Find all the possiible substrings.

Approaches (3)

Approach 1

Approach 2

Approach 3

Approach1

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 .

Time Complexity

O(N ^ 3), where ‘N’ is the length of the string.

There are a total N ^ 2 substrings and increasing the count of each substring takes O(N) time.

Thus time complexity is O(N ^ 3).

Space Complexity

O(N ^ 2), Where N is the length of the string.

We are storing each substring and there are a total of N ^ 2 substrings. Thus space complexity will be O(N ^ 2).

(100% EXP penalty)

Longest Duplicate SubString

Console