Longest Repeating Substring

medium dynamic programming string

Problem

Given a string s, return the length of the longest repeating substring. A repeating substring is one that occurs in s at least twice (the two occurrences may overlap, but must start at different indices). If no repeating substring exists, return 0.

Inputs = "abcabcd"

Output3

"abc" occurs twice (at index 0 and index 3), so the answer is its length 3.

s (lowercase letters)

def longest_repeating_substring(s):
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if s[i - 1] == s[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])
    return best

function longestRepeatingSubstring(s) {
  const n = s.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = i + 1; j <= n; j++) {
      if (s[i - 1] === s[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        best = Math.max(best, dp[i][j]);
      }
    }
  }
  return best;
}

class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        int best = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (s.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    best = Math.max(best, dp[i][j]);
                }
            }
        }
        return best;
    }
}

int longestRepeatingSubstring(string s) {
    int n = s.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    int best = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (s[i - 1] == s[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                best = max(best, dp[i][j]);
            }
        }
    }
    return best;
}

Explanation

We want the longest substring that shows up twice in the string. The clever framing is to compare the string with itself and look for matching runs that start at two different positions.

We build a table where dp[i][j] means: how long is the matching run that ends at position i-1 and at position j-1. If the two characters at those positions match, the run just extends the previous diagonal: dp[i][j] = dp[i-1][j-1] + 1. If they differ, the run is broken and stays 0.

To make sure the two copies start at different places, we only fill cells where j > i. That keeps the two pointers apart and avoids matching a character with itself.

We track the biggest value any cell reaches in best; that number is the length of the longest substring appearing in two spots. It works because a repeated substring of length L always produces a diagonal chain of L growing matches in this table.

Example: in "abcabcd", the "abc" at index 0 and the "abc" at index 3 line up into a diagonal run that reaches 3, so the answer is 3.

Time: O(n²) Space: O(n²)