Longest Repeating Substring

Problem

Return the length of the longest substring of s that occurs at least twice; the two occurrences may overlap.

Use dynamic programming where dp[i][j] extends dp[i-1][j-1] when s[i-1] equals s[j-1] and the two positions are different. Return 0 when no character repeats.

Hint

Restricting the inner loop to j > i guarantees the two occurrences start at different positions.

Test cases

case 1

in: ["abcd"]

expected: 0

case 2

in: ["abbaba"]

expected: 2

case 3

in: ["aabcaabdaab"]

expected: 3

case 4

in: [""]

expected: 0

case 5

in: ["aaaaa"]

expected: 4

Starter codePython

def longest_repeating_substring(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor