Introduction

The longest repeated substring problem asks for the longest substring that appears at least twice in the same string. Suffix trees and suffix arrays are classic high-performance solutions, but they are not the only workable approach.

If you want something easier to implement, dynamic programming is a practical alternative. It costs more memory, but for moderate input sizes it is simple, correct, and much easier to explain in an interview or code review.

A Dynamic Programming Idea

The problem resembles longest common substring, except the string is compared with itself at different positions. If s[i] == s[j], then a repeated suffix ending at those positions can extend a previous match.

Define dp[i][j] as the length of the common suffix ending at positions i - 1 and j - 1. Then:

dp[i][j] = dp[i - 1][j - 1] + 1   if s[i - 1] == s[j - 1] and i != j
dp[i][j] = 0                      otherwise

The i != j condition stops the algorithm from matching a character with itself at the same location.

Basic Implementation

1def longest_repeated_substring(s):
2    n = len(s)
3    dp = [[0] * (n + 1) for _ in range(n + 1)]
4    best_len = 0
5    best_end = 0
6
7    for i in range(1, n + 1):
8        for j in range(1, n + 1):
9            if i != j and s[i - 1] == s[j - 1]:
10                dp[i][j] = dp[i - 1][j - 1] + 1
11                if dp[i][j] > best_len:
12                    best_len = dp[i][j]
13                    best_end = i
14
15    return s[best_end - best_len:best_end]
16
17
18print(longest_repeated_substring("banana"))

Output:

ana

"ana" appears twice in "banana", once starting at index 1 and once at index 3.

Why It Works

Whenever two characters match at different positions, the repeated substring ending there can extend the repeated substring that ended one character earlier at both positions. That is exactly what the recurrence captures.

The algorithm checks every pair of positions, so it finds the best repeated substring anywhere in the string, not just near the front.

For "banana":

• matching a with later a starts a repetition
• matching n with later n extends that repetition
• matching the next a extends again

That gives "ana" with length 3.

Space Optimization

The full table uses O(n^2) memory. If you only need the best length and substring, you can reduce space to O(n) by keeping only the previous row.

1def longest_repeated_substring_optimized(s):
2    n = len(s)
3    prev = [0] * (n + 1)
4    best_len = 0
5    best_end = 0
6
7    for i in range(1, n + 1):
8        curr = [0] * (n + 1)
9        for j in range(1, n + 1):
10            if i != j and s[i - 1] == s[j - 1]:
11                curr[j] = prev[j - 1] + 1
12                if curr[j] > best_len:
13                    best_len = curr[j]
14                    best_end = i
15        prev = curr
16
17    return s[best_end - best_len:best_end]

This has the same O(n^2) time complexity but much better memory usage.

Overlapping vs Non-Overlapping Repetitions

One subtle point is whether overlaps are allowed. The basic dynamic programming solution above allows overlapping matches. That is why "ana" is valid in "banana".

If you need non-overlapping repeated substrings, cap the DP value so a match cannot grow beyond the distance between the two occurrences:

1def longest_non_overlapping_repeated_substring(s):
2    n = len(s)
3    dp = [[0] * (n + 1) for _ in range(n + 1)]
4    best_len = 0
5    best_end = 0
6
7    for i in range(1, n + 1):
8        for j in range(i + 1, n + 1):
9            if s[i - 1] == s[j - 1]:
10                dp[i][j] = min(dp[i - 1][j - 1] + 1, j - i)
11                if dp[i][j] > best_len:
12                    best_len = dp[i][j]
13                    best_end = i
14
15    return s[best_end - best_len:best_end]

That version is important if the problem statement forbids overlaps explicitly.

When This Is Good Enough

The dynamic programming approach is often good enough when:

• the input string is moderate in length
• implementation clarity matters more than asymptotic optimality
• you are solving a one-off problem, not building a heavy-duty text index

For very large strings, suffix arrays, suffix automata, or suffix trees are better because O(n^2) time and memory eventually become too expensive.

Common Pitfalls

The biggest pitfall is forgetting i != j. Without that condition, the algorithm will match the string with itself at the same position and return the whole string incorrectly.

Another common issue is not deciding whether overlap is allowed. "ana" in "banana" is valid for the overlapping version but not for the non-overlapping version.

Developers also sometimes update the best substring using the wrong ending index. Keep track of where the winning match ends so you can slice the string correctly afterward.

Finally, do not use the quadratic dynamic programming approach for huge inputs without thinking about memory. A table for a string of length 50,000 is already impractical.

Summary

• You can solve longest repeated substring without suffix arrays or suffix trees by dynamic programming.
• The core idea is longest common substring on the string against itself with i != j.
• The straightforward solution uses O(n^2) time and O(n^2) space.
• A rolling-row version reduces memory to O(n).
• Decide whether the problem allows overlapping repeated substrings.
• For moderate input sizes, the dynamic programming approach is simple and effective.