Given a string S, 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.  Print the longest non-overlapping substring. If no such substring exists print -1.
Note: Multiple Answers are possible but you have to print the substring which occurs atleat twice first.
For Example: "ablhiabohi". Here both "ab" and "hi" are possible answers. But you will have to return "ab" as because it repeats before "hi".
 
Example 1:
Input:
N = 13
S = "geeksforgeeks"
Output:
geeks
Explanation:
The string "geeks" is the longest Substring
of S which is repeating but not overlapping.
Example 2:
Input:
N = 8
S = "heyhheyi"
Output:
hey
Explanation:
The string "hey" is the longest Substring
of S which is repeating but not overlapping.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestSubstring() which takes a Integer N and a String S as input and returns the answer.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1 <= N <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def longestSubstring(self, S , N):
        # code here 

Solutions:
class Solution:

	def longestSubstring(self, S, N):
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		max_len = 0
		res = ''
		for i in range(N):
			for j in range(i + 1, N):
				if S[i] == S[j] and dp[i][j] < j - i:
					dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
					if dp[i + 1][j + 1] > max_len:
						max_len = dp[i + 1][j + 1]
						res = S[i - max_len + 1:i + 1]
		return res if len(res) > 0 else -1


class Solution:

	def longestSubstring(self, str, N):
		n = len(str)
		LCSRe = [[0 for x in range(n + 1)] for y in range(n + 1)]
		res = ''
		res_length = 0
		index = 0
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if str[i - 1] == str[j - 1] and LCSRe[i - 1][j - 1] < j - i:
					LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
					if LCSRe[i][j] > res_length:
						res_length = LCSRe[i][j]
						index = max(i, index)
				else:
					LCSRe[i][j] = 0
		if res_length > 0:
			for i in range(index - res_length + 1, index + 1):
				res = res + str[i - 1]
			return res
		return -1


class Solution:

	def lcs(self, x, y, n):
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		max_length = 0
		start = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if x[i - 1] == y[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if max_length < dp[i][j]:
						max_length = dp[i][j]
						start = i - max_length
		if max_length == 0:
			return -1
		return x[start:start + max_length]

	def longestSubstring(self, S, N):
		ans = self.lcs(S, S, N)
		return ans


class Solution:

	def longestSubstring(self, S, N):
		t = [['' for i in range(N + 1)] for j in range(N + 1)]
		res = ''
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if S[i - 1] == S[j - 1] and i != j:
					t[i][j] = t[i - 1][j - 1] + S[i - 1]
					res = max(res, t[i][j], key=len)
				else:
					t[i][j] = ''
		if res == '':
			return -1
		return res


class Solution:

	def longestSubstring(self, S, N):
		temp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		res = ''
		res_length = 0
		ind = 0
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if S[i - 1] == S[j - 1] and temp[i - 1][j - 1] < j - i:
					temp[i][j] = temp[i - 1][j - 1] + 1
					if temp[i][j] > res_length:
						res_length = temp[i][j]
						ind = max(ind, i)
				else:
					temp[i][j] = 0
		for i in range(ind - res_length, ind):
			res += S[i]
		return res if res != '' else -1


class Solution:

	def longestSubstring(self, S, N):
		dp = [[0 for i in range(N)] for i in range(N)]
		maxi = (0, 0)
		for i in range(N):
			for j in range(i + 1, N):
				if S[i] == S[j] and j - i > dp[i - 1][j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if dp[i][j] > maxi[1]:
						maxi = (i, dp[i][j])
		if maxi == (0, 0):
			return -1
		return ''.join(S[maxi[0] - maxi[1] + 1:maxi[0] + 1])


class Solution:

	def longestSubstring(self, S, N):
		index = 0
		dp = [[0 for _ in range(N + 1)] for j in range(N + 1)]
		res = 0
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if S[i - 1] == S[j - 1] and dp[i - 1][j - 1] < j - i:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if dp[i][j] > res:
						res = dp[i][j]
						index = max(index, i)
		result = ''
		if res > 0:
			result = S[index - res:index]
			return result
		else:
			return -1


class Solution:

	def longestSubstring(self, S, N):
		s2 = S[:]
		l = [[0 for i in range(N + 1)] for j in range(N + 1)]
		p = 0
		st = -1
		for i in range(N + 1):
			for j in range(N + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif S[i - 1] == s2[j - 1] and i != j:
					l[i][j] = l[i - 1][j - 1] + 1
					if l[i][j] > p:
						p = l[i][j]
						st = i - p
				else:
					l[i][j] = 0
		if p == 0:
			return '-1'
		return S[st:st + p]


class Solution:

	def longestSubstring(self, S, N):
		str_a = S
		str_b = S
		r = len(str_a)
		c = r
		str_b = str_a
		dp = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
		for i in range(r):
			dp[i][0] = 0
		for j in range(c):
			dp[0][j] = 0
		max_ = 0
		ind = 0
		for i in range(1, r + 1):
			for j in range(1, c + 1):
				if str_a[i - 1] == str_b[j - 1] and i != j:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if max_ < dp[i][j]:
						ind = i
					max_ = max(max_, dp[i][j])
				else:
					dp[i][j] = 0
		if max_ == 0:
			return -1
		end = ind
		start = end - max_
		return str_a[ind - max_:ind]


class Solution:

	def longestSubstring(self, s1, N):
		s2 = s1
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		res_len = 0
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if s1[i - 1] == s2[j - 1]:
					x = 1 + dp[i - 1][j - 1]
					if x < j - i:
						dp[i][j] = x
						if x > res_len:
							res_len = x
							ending_idx = i
					else:
						dp[i][j] = 0
		res = []
		if res_len > 0:
			for i in range(ending_idx - res_len + 1, ending_idx + 1):
				res.append(s1[i - 1])
			return ''.join(res)
		return -1


class Solution:

	def longestSubstring(self, s1, N):
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		res = []
		res_len = 0
		idx = 0
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if s1[i - 1] == s1[j - 1] and dp[i - 1][j - 1] < j - i:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > res_len:
						res_len = dp[i][j]
						idx = max(i, idx)
				else:
					dp[i][j] = 0
		if res_len > 0:
			for i in range(idx - res_len + 1, idx + 1):
				res.append(s1[i - 1])
			return ''.join(res)
		else:
			return -1


class Solution:

	def longestSubstring(self, s, n):
		n = len(s)
		l = 0
		ans = ''
		(x, y) = (-1, -1)
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if s[i - 1] == s[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if l < dp[i][j]:
						l = dp[i][j]
						x = i
						y = j
		while x > 0 and y > 0:
			if s[x - 1] == s[y - 1]:
				ans = s[x - 1] + ans
			if len(ans) == l:
				return ans
			x -= 1
			y -= 1
		return -1


class Solution:

	def longestSubstring(self, S, N):
		t = []
		ans = []
		for j in range(N + 1):
			ans.append(-1)
		for i in range(N + 1):
			a = ans.copy()
			t.append(a)
		maxi = 0
		x = 0
		y = 0
		for i in range(N + 1):
			for j in range(N + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif S[i - 1] == S[j - 1] and i != j:
					t[i][j] = 1 + t[i - 1][j - 1]
					if maxi < max(maxi, t[i][j]):
						maxi = max(maxi, t[i][j])
						x = i
						y = j
				else:
					t[i][j] = 0
		if x == 0 and y == 0:
			return -1
		i = x
		j = y
		ans = ''
		while i >= 0 and j >= 0 and (t[i][j] != 0):
			ans = S[j - 1] + ans
			i -= 1
			j -= 1
		return ans


class Solution:

	def longestSubstring(self, s, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		ans = 0
		a = -1
		for i in range(1, n):
			if s[i] == s[0]:
				dp[0][i] = 1
				if ans < dp[0][i]:
					ans = dp[0][i]
					a = 0
		for i in range(1, n):
			for j in range(i + 1, n):
				if s[i] == s[j]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = 0
				if ans < dp[i][j]:
					ans = dp[i][j]
					a = i
		ans1 = ''
		if a == -1:
			return -1
		for i in range(a, a - ans, -1):
			ans1 += s[i]
		return ans1[::-1]


class Solution:

	def longestSubstring(self, s, N):
		dp = [[0 for i in range(len(s) + 1)] for i in range(len(s) + 1)]
		maxi = 0
		index = -1
		for i in range(1, len(s) + 1):
			for j in range(i + 1, len(s) + 1):
				if s[i - 1] == s[j - 1] and j - i > dp[i - 1][j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > maxi:
						maxi = dp[i][j]
						index = i - maxi
		if len(s[index:index + maxi]) == 0:
			return -1
		return s[index:index + maxi]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.longestSubstring(S, N))


class Solution:

	def longestSubstring(self, S, N):
		res_len = 0
		res = ''
		idx = 0
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if S[i - 1] == S[j - 1] and dp[i - 1][j - 1] < j - i:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if dp[i][j] > res_len:
						res_len = dp[i][j]
						idx = max(i, idx)
				else:
					dp[i][j] = 0
		if res_len > 0:
			for i in range(idx - res_len + 1, idx + 1):
				res += S[i - 1]
		else:
			return -1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.longestSubstring(S, N))


class Solution:

	def longestSubstring(self, s, n):
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		(result, resultLength, index) = ('', 0, 0)
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if s[i - 1] == s[j - 1] and dp[i - 1][j - 1] < j - i:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > resultLength:
						resultLength = dp[i][j]
						index = max(i, index)
				else:
					dp[i][j] = 0
		if resultLength > 0:
			for i in range(index - resultLength + 1, index + 1):
				result += s[i - 1]
		return result if resultLength > 0 else -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.longestSubstring(S, N))


from functools import lru_cache

class Solution:

	def longestSubstring(self, s, n):
		ans = 0
		n = len(s)

		@lru_cache()
		def dfs(i, j):
			if j == n:
				return 0
			if s[i] == s[j]:
				ans = 1 + dfs(i + 1, j + 1)
				if ans > j - i:
					return 0
				else:
					return ans
			else:
				return 0
		res = None
		for i in range(n):
			for j in range(i + 1, n):
				t = dfs(i, j)
				if t > ans:
					ans = t
					res = i
		return s[res:res + ans] if res != None else '-1'


class Solution:

	def longestSubstring(self, S, N):
		m = [[0] * (N + 1) for i in range(N + 1)]
		maxLen = 0
		maxStart = 0
		for i in range(N):
			for j in range(i + 1, N):
				if S[i] == S[j]:
					countHere = m[i][j] + 1
					m[i + 1][j + 1] = countHere
					if countHere > maxLen and j - i >= countHere:
						maxLen = countHere
						maxStart = i + 1 - countHere
				else:
					m[i + 1][j + 1] = 0
		if maxLen > 0:
			return S[maxStart:maxStart + maxLen]
		else:
			return '-1'


class Solution:

	def longestSubstring(self, S, N):
		size = 0
		res = ''
		start = 0
		dp = [[0 for i in range(N + 1)] for i in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if S[i - 1] == S[j - 1] and dp[i - 1][j - 1] < j - i:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > size:
						size = dp[i][j]
						start = max(start, i)
				else:
					dp[i][j] = 0
		if size > 0:
			for i in range(start - size + 1, start + 1):
				res += S[i - 1]
		else:
			return -1
		return res


class Solution:

	def longestSubstring(self, s, n):
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		maxl = 0
		ind = 0
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if s[i - 1] == s[j - 1] and j - i > dp[i - 1][j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				if maxl < dp[i][j]:
					maxl = dp[i][j]
					ind = max(ind, i)
		res = ''
		if maxl > 0:
			ind -= 1
			for i in range(maxl):
				res += s[ind]
				ind -= 1
		return res[::-1] if res else -1


class Solution:

	def longestSubstring(self, s, n):
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		res = ''
		res_len = 0
		idx = 0
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if s[i - 1] == s[j - 1] and dp[i - 1][j - 1] < j - 1:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > res_len:
						res_len = dp[i][j]
						idx = max(idx, i)
				else:
					dp[i][j] = 0
		if res_len > 0:
			for i in range(idx - res_len + 1, idx + 1):
				res += s[i - 1]
		return -1 if len(res) == 0 else res


class Solution:

	def longestSubstring(self, s, n):
		dp = [[0] * (n + 1) for i in range(n + 1)]
		(mi, mj) = (0, 0)
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if s[i - 1] == s[j - 1] and j - i > dp[i - 1][j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					if dp[i][j] > dp[mi][mj]:
						(mi, mj) = (i, j)
				else:
					dp[i][j] = 0
		if dp[mi][mj] < 1:
			return -1
		return s[mj - dp[mi][mj]:mj]


class Solution:

	def longestSubstring(self, s, n):
		a = []
		maxv = -1
		maxi = -1
		for i in range(n):
			lst = []
			for j in range(n):
				if i == 0 and j != 0 and (s[0] == s[j]):
					lst.append(1)
					maxv = 1
					maxi = j
				else:
					lst.append(0)
			a.append(lst)
		for i in range(1, n):
			for j in range(i + 1, n):
				if s[i] == s[j]:
					a[i][j] = min(1 + a[i - 1][j - 1], j - i)
					if maxv < a[i][j]:
						maxv = a[i][j]
						maxi = j
		if maxi == -1:
			return -1
		else:
			return s[maxi - maxv + 1:maxi + 1]


class Solution:

	def longestSubstring(self, S, N):
		maxString = ''
		for i in range(N):
			for j in range(i + 1, N):
				if S[i] == S[j]:
					x = i + 1
					y = j + 1
					newMax = S[i]
					while y < N and S[x] == S[y]:
						newMax += S[x]
						x += 1
						y += 1
					if len(maxString) < len(newMax):
						maxString = newMax
		if len(maxString) == 0:
			return -1
		return maxString


class Solution:

	def longestSubstring(self, s1, N):
		res = ''
		s2 = s1[:]
		k = 0
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if s1[i - 1] == s2[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if k < dp[i][j]:
						k = dp[i][j]
						index = i - k
		if k <= 0:
			return -1
		for i in range(index, index + k):
			res += s1[i]
		return res


class Solution:

	def longestSubstring(self, s, N):
		ans = ''
		j = 1
		for i in range(len(s)):
			longest = s[i:i + j]
			temp = s[i + 1:]
			while longest in temp:
				ans = longest
				j += 1
				longest = s[i:i + j]
		if len(ans) == 0:
			return -1
		else:
			return ans


class Solution:

	def longestSubstring(self, S, N):
		y = ''
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(i + 1, N + 1):
				if S[i - 1] == S[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
					x = S[j - dp[i][j]:j]
					if dp[i][j] > len(y):
						y = x
				else:
					dp[i][j] = 0
		if not y:
			return -1
		return y


class Solution:

	def longestSubstring(self, S, N):
		dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
		maxi = -10 ** 9
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				if S[i - 1] == S[j - 1] and i != j:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > maxi:
						end = j
						maxi = dp[i][j]
				else:
					dp[i][j] = 0
		if maxi == -10 ** 9:
			return -1
		s = S[end - maxi:end]
		return s