Last Updated: 1 Dec, 2020
Longest Repeating Non-Overlapping Substring.
Easy
Asked in company
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).
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
Approaches
- 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.
- Create an auxiliary matrix of size N x N, let’s call it dp[N][N].
- dp[i][j] stores the maximum length of repeating non-overlapping substring ending at ith and jth indexes in the given input word, where j > i.
- Let’s initialize the dp matrix with 0.
- Let’s also define, ans = 0 (stores length of maximum repeating non-overlapping substring), start = 0, end = 0 denoting the start and end indices of the solution string.
- Then for indexes i and j, one of the below mentioned two conditions can be true:
- If the ith and jth characters are both equal, and dp[i-1][j-1] != 0, that means we have already continued a substring comparison. But before increasing the required substring length, check for the non-overlapping condition. The substrings ending at i-1 th and j-1 th indexes will be non-overlapping if the difference between j-1th and i-1 th indexes >= dp[i-1][j-1] i.e. the length of the second substring should lie well within [i+1, j-1] if the current comparison of substrings ending at ith and jth indices is taking place. Also, after each step maximise the length of the answer and start index as i, if the maximum length is changed.
- If the ith and jth characters in the given word are not the same, then continue.
- Finally if the length of our solution string stored by “len” variable == 0, then return an empty string.
- Else, if the length >= 1, create auxiliary string sol and append all characters from start till end indices.