Problem statement

https://leetcode.com/problems/longest-repeating-substring/

Solution

Actually, this problem is simple case of 1044. Longest Duplicate Substring, here constraints are smaller. We can use rolling hash algorithm with O(n log n) complexity, but it is enough to have dp with dp(i, j) be an answer to question: what is the length of maximum substrings ending with places i and j.

Complexity

It is O(n^2) both for time and space.

Code

class Solution:
    def longestRepeatingSubstring(self, s):
        n, ans = len(s), 0
        dp = [[0] * (n+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, i):
                if s[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    ans = max(ans, dp[i][j])

        return ans