Problem Description

Given a string s, you need to find the length of the longest substring that appears at least twice in the string. The repeating substrings can overlap but must start at different positions.

For example:

• In the string "abcabc", the substring "abc" appears twice (at positions 0 and 3), so the answer would be 3
• In the string "aabcaaba", the substring "aab" appears twice (at positions 0 and 5), so the answer would be 3
• In the string "abbaba", the substring "ab" appears multiple times, and "ba" also appears multiple times, but the longest repeating substring is "ab" or "ba" with length 2
• If no substring repeats (like in "abcd"), return 0

The key insight is that we're looking for the longest common substring between the string and itself, but ensuring the two occurrences start at different positions. The solution uses dynamic programming where f[i][j] represents the length of the longest common substring ending at positions i and j where i > j. When characters at positions i and j match (s[i] == s[j]), we extend the previous matching substring length by 1. The condition i > j ensures we're comparing different positions in the string.

Intuition

The problem asks for the longest substring that appears at least twice. This immediately suggests we need to compare the string with itself to find common substrings at different positions.

Think of it this way: if we have a repeating substring, it means there are two positions i and j in the string where the same sequence of characters begins. For example, in "banana", both positions 1 and 3 start with "ana".

This naturally leads to a dynamic programming approach where we compare every pair of positions in the string. We can build a 2D table where f[i][j] tracks the length of matching substrings ending at positions i and j.

The key insight is that if characters at positions i and j match (s[i] == s[j]), we can extend any matching substring that ended at positions i-1 and j-1. This is similar to finding the longest common subsequence, but here we're looking for consecutive matches.

Why do we only consider j < i? Because we want to avoid comparing a position with itself (which would always match) and we don't need to check both (i,j) and (j,i) since they represent the same pair of substrings.

The recurrence relation becomes clear: if s[i] == s[j], then f[i][j] = f[i-1][j-1] + 1 (extending the previous match by one character). Otherwise, the matching substring ends, so we don't update f[i][j] (it remains 0).

By tracking the maximum value across all f[i][j], we find the length of the longest repeating substring in the entire string.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D table to track matching substrings.

Step 1: Initialize the DP table

Create a 2D array f of size n × n where n is the length of string s. Initialize all values to 0. Here, f[i][j] represents the length of the longest repeating substring ending at positions i and j.

Step 2: Fill the DP table

We iterate through all pairs of positions where i ranges from 1 to n-1 and j ranges from 0 to i-1. This ensures we only compare different positions and avoid redundant comparisons.

For each pair (i, j):

• If s[i] == s[j], we found matching characters at different positions
• We update f[i][j] based on whether we can extend a previous match:

The formula means:

• When j > 0: We can check if there was a match at (i-1, j-1). If yes, we extend that substring by 1
• When j = 0: We're at the boundary, so the matching substring has length 1

Step 3: Track the maximum length

As we fill the table, we continuously update ans with the maximum value found in f[i][j]. This gives us the length of the longest repeating substring.

Example walkthrough:

For string "aab":

• When i=1, j=0: s[1]='a' equals s[0]='a', so f[1][0] = 1
• When i=2, j=0: s[2]='b' ≠ s[0]='a', so f[2][0] = 0
• When i=2, j=1: s[2]='b' ≠ s[1]='a', so f[2][1] = 0

The maximum value is 1, which corresponds to the repeating substring "a".

Time Complexity: O(n²) - We iterate through all pairs (i, j) where i > j

Space Complexity: O(n²) - We use a 2D array of size n × n

Example Walkthrough

Let's walk through the solution with the string s = "ababa".

Step 1: Initialize

• String: "ababa" (indices 0-4)
• Create a 5×5 DP table f, initialized with zeros
• ans = 0

Step 2: Fill the DP table

We iterate through pairs (i, j) where i > j:

When i = 1:

• j = 0: Compare s[1]='b' with s[0]='a' → Different, f[1][0] = 0

When i = 2:

• j = 0: Compare s[2]='a' with s[0]='a' → Match! f[2][0] = 1, update ans = 1
• j = 1: Compare s[2]='a' with s[1]='b' → Different, f[2][1] = 0

When i = 3:

• j = 0: Compare s[3]='b' with s[0]='a' → Different, f[3][0] = 0
• j = 1: Compare s[3]='b' with s[1]='b' → Match! Since f[2][0] = 1 (previous positions matched), f[3][1] = f[2][0] + 1 = 2, update ans = 2
• j = 2: Compare s[3]='b' with s[2]='a' → Different, f[3][2] = 0

When i = 4:

• j = 0: Compare s[4]='a' with s[0]='a' → Match! Since f[3][0] = 0 (no previous match), f[4][0] = 0 + 1 = 1
• j = 1: Compare s[4]='a' with s[1]='b' → Different, f[4][1] = 0
• j = 2: Compare s[4]='a' with s[2]='a' → Match! Since f[3][1] = 2 (previous positions matched), f[4][2] = f[3][1] + 1 = 3, update ans = 3
• j = 3: Compare s[4]='a' with s[3]='b' → Different, f[4][3] = 0

Final DP table (showing non-zero values):

    0  1  2  3  4
0   0  -  -  -  -
1   0  0  -  -  -
2   1  0  0  -  -
3   0  2  0  0  -
4   1  0  3  0  0

Result: The maximum value is 3, corresponding to the substring "aba" which appears at positions 0-2 and 2-4.

The key insight: When we found f[4][2] = 3, it means the substrings ending at positions 4 and 2 share 3 consecutive matching characters. Working backwards: s[4]=s[2]='a', s[3]=s[1]='b', s[2]=s[0]='a', giving us the repeating substring "aba".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses two nested loops. The outer loop runs from index 1 to n-1, iterating n-1 times. The inner loop runs from index 0 to i-1 for each iteration of the outer loop. This gives us a total of 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 iterations, which simplifies to O(n²) time complexity.

Space Complexity: O(n²)

The algorithm creates a 2D array f of size n × n to store the dynamic programming states, where f[i][j] represents the length of the longest common substring ending at positions i and j. This requires O(n²) space. The only other variables used are ans and loop counters, which take O(1) additional space. Therefore, the overall space complexity is O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Overlapping vs Non-overlapping Substrings

A common misunderstanding is thinking that repeating substrings cannot overlap at all. In reality, they can overlap as long as they start at different positions.

Incorrect assumption: In string "aaa", thinking the answer is 1 because substrings cannot overlap.

Correct understanding: The substring "aa" appears at positions 0 and 1 (overlapping), so the answer is 2.

2. Incorrect DP State Definition

Some might try to define dp[i][j] for all i and j, leading to redundant calculations or incorrect results when i == j.

Pitfall code:

for i in range(n):
    for j in range(n):
        if i != j and s[i] == s[j]:  # Wrong: includes both (i,j) and (j,i)
            dp[i][j] = dp[i-1][j-1] + 1

Solution: Always maintain i > j to avoid counting the same pair twice and to ensure we're comparing different starting positions:

for i in range(1, n):
    for j in range(i):  # Ensures j < i
        if s[i] == s[j]:
            dp[i][j] = dp[i-1][j-1] + 1 if j > 0 else 1

3. Space Optimization Trap

Attempting to optimize space by using a 1D array instead of 2D without careful consideration of dependencies.

Incorrect optimization:

dp = [0] * n  # Wrong: loses information about different starting positions
for i in range(1, n):
    if s[i] == s[i-1]:
        dp[i] = dp[i-1] + 1  # This only finds consecutive repeating characters

Correct space optimization: If space is a concern, use a rolling array technique:

prev = [0] * n
curr = [0] * n
for i in range(1, n):
    for j in range(i):
        if s[i] == s[j]:
            curr[j] = prev[j-1] + 1 if j > 0 else 1
            max_length = max(max_length, curr[j])
    prev, curr = curr, [0] * n

4. Edge Case Handling

Forgetting to handle strings with length 0 or 1, which cannot have repeating substrings.

Missing edge case:

def longestRepeatingSubstring(self, s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # Fails when n = 0

Solution:

def longestRepeatingSubstring(self, s: str) -> int:
    n = len(s)
    if n < 2:
        return 0
    dp = [[0] * n for _ in range(n)]