Longest Repeating Non-Overlapping Substring.

Easy

0/40

1 upvote

Asked in company

Problem statement

You are given a string ‘str’, you need to find the longest repeating and non-overlapping substring in the given string.

A substring of a string can be defined as a contiguous subsequence of that string. In other words, a string X is said to be a substring of the string S if X = S[a...b] = S[a]S[a+1]…..S[b] and 0 <= a <= b <= len(S) (0-based indexing).

You can return any such substring if more than one such substring exists in the string. If there is no such substring, return -1.

Note:

1. Repeating substrings in a string means those substrings which occur more than once in a string. For example, in the string “abaaba”, substrings “a”, “b”, “ab”, “ba”, “aba” are repeating.

2. Two substrings are called Non-overlapping substrings, if the intersection of all the indices of first substring i.e. [L1, R1] where L1 and R1 are the starting and ending index of the first substring respectively, and indices of the second substring i.e. [L2, R2] where L2 and R2 are the starting and ending indices respectively of the second substring, is NULL.

3. For example, in the string “abaaba”, two non-overlapping strings are “ab” lying in the interval [0, 1] (0-based indexing) and “aba” lying in the interval [3, 5] (0-based indexing).

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

Input Format:

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

The first and the only line of each test case contains the string str, whose longest repeating non-overlapping substring is to be found.

Output Format:

The only line of output of each test case should contain a string representing the longest repeating non-overlapping substring of the input string or -1 if no such substring exists.

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 <= len(S) <= 100    
Time Limit: 1sec

Sample Input 1:

1
abaaba

Sample Output 1:

aba

Explanation for Sample Input 1:

The substring “aba” of length 3, is present twice in the given string and also both the occurrences are non-overlapping to each other.

Sample Input 2:

1
codingninjassajningnidoc

Sample Output 2:

ingni

Explanation for Sample Input 2:

The substring “ingni” of length 5, is maximum repeating non-overlapping substring in the given word and occurs twice.

Approaches (2)

Approach 1

Approach 2

Try all possible substrings.

To find the longest repeating non-overlapping substring, we need to first find all the substrings.
We can do this using two pointer approach in O(N^2) time.
Now for each substring starting at say index i and ending at index j where i <= j, compare it with all the remaining substrings in the given word, which start at indices >= j+1 and are of the same length as that of a substring starting at i.
If the two strings match, then this given substring is one of our possible answers, store it in a solution string and continue the process.
If at the end of the iteration, the solution string is still empty, that means there is no repeating non-overlapping substring and return an empty solution string.

Time Complexity

O(N^3), where N is the length of the input string word.

Space Complexity

O(N), as we use auxiliary space to store solution string, where N is the length of the input string str.

(100% EXP penalty)

Longest Repeating Non-Overlapping Substring.

Console