# Introduction

Given a string str, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. If there exists more than one such substring return any of them.

# Approach

There are two approaches for the given problem. We can take the DP approach or the LPS (Longest possible suffix which is also a prefix and preprocessing of KMP algorithm).

## DP based

The idea is look for each letter repeating in the string and update the DP array.

In the below example we go letter by lettter and compares with the next letters,

- If a match is found we add 1 and previous element repeat count

Previous element is diagonally up left, which is 0 for the first row - If a match is not found we set it to 0

**Note:** A condition is added to make sure the range is not overlapping by using the `j-1`

and previous dp count.

^{2}

Space Complexity: O(n)

^{2}

## LPS based (KMP Preprocessing)

This approach is based on the preprocessing for the KMP using the LPS (longest possible suffix which is also a prefix)

Below implementation uses the `start`

variable to use instead of 0 in case of normal LPS implementations.

```
using System;
public class GFG {
public static void Main()
{
var t = int.Parse(Console.ReadLine() ?? "0");
while (t-- > 0)
{
var n = int.Parse(Console.ReadLine() ?? "0");
var str = Console.ReadLine();
Console.WriteLine(MaxRepeatNonOverlapSubstrLps(str, n));
}
}
private static string MaxRepeatNonOverlapSubstrLps(string str, int n)
{
if (string.IsNullOrEmpty(str))
{
return str;
}
var index = 0;
var max = 0;
var lps = new int[n];
for (var start = 0; start < n; start++)
{
var i = start;
for (var j = i + 1; j < n; )
{
if (str[i] == str[j])
{
// Added for non overlapping
if (j - i > i - start)
{
lps[j] = i - start + 1;
if (lps[j] > max)
{
max = lps[j];
index = start;
}
i++;
j++;
}
else
{
i = lps[i];
}
}
else if (i != start) // start is used instead of 0
{
i = lps[i - 1];
if (i < start) // set the start
{
i = start;
}
}
else
{
lps[j] = 0;
j++;
}
}
Array.Clear(lps, 0, lps.Length);
}
return max > 0 ? str.Substring(index, max) : "-1";
}
}
```

Time Complexity:
O(n)^{2}

Space Complexity: O(n)