BinarySearch 0818 Longest Repeating Substring

Problem statement

https://binarysearch.com/problems/Longest-Repeating-Substring/

Solution

Equal to Leetcode 1062 Longest Repeating Substring.

Complexity

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

Code

class Solution:
    def solve(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