Skip to content

1062. Longest Repeating Substring πŸ”’

Description

Given a string s, return the length of the longest repeating substrings. If no repeating substring exists, return 0.

 

Example 1:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

Example 2:

Input: s = "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.

Example 3:

Input: s = "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.

 

Constraints:

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters.

Solutions

Solution 1: Dynamic Programming

Thinking

A longest repeated substring can use a suffix array or hashed binary search; \(n\le 2000\) also allows an \(O(n^2)\) DP. The common suffix ending at distinct \(i>j\) grows by one when \(s[i]=s[j]\).

\(f[i][j]\) is that length. Enumerate \(i\) and \(j<i\), transfer on equality, and track the global maximum.

The answer is the largest \(f[i][j]\).

We define \(f[i][j]\) to represent the length of the longest repeating substring ending with \(s[i]\) and \(s[j]\). Initially, \(f[i][j]=0\).

We enumerate \(i\) in the range \([1, n)\) and enumerate \(j\) in the range \([0, i)\). If \(s[i]=s[j]\), then we have:

\[ f[i][j]= \begin{cases} f[i-1][j-1]+1, & j>0 \\ 1, & j=0 \end{cases} \]

The answer is the maximum value of all \(f[i][j]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Where \(n\) is the length of the string \(s\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for j in range(i):
                if s[i] == s[j]:
                    f[i][j] = 1 + (f[i - 1][j - 1] if j else 0)
                    ans = max(ans, f[i][j])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = 1 + (j > 0 ? f[i - 1][j - 1] : 0);
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int n = s.length();
        int f[n][n];
        memset(f, 0, sizeof(f));
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = 1 + (j > 0 ? f[i - 1][j - 1] : 0);
                    ans = max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func longestRepeatingSubstring(s string) (ans int) {
    n := len(s)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if s[i] == s[j] {
                if j > 0 {
                    f[i][j] = f[i-1][j-1]
                }
                f[i][j]++
                ans = max(ans, f[i][j])
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function longestRepeatingSubstring(s: string): number {
    const n = s.length;
    const f: number[][] = Array.from({ length: n }).map(() => Array(n).fill(0));
    let ans = 0;
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (s[i] === s[j]) {
                f[i][j] = 1 + (f[i - 1][j - 1] || 0);
                ans = Math.max(ans, f[i][j]);
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn longest_repeating_substring(s: String) -> i32 {
        let n = s.len();
        let mut f = vec![vec![0; n]; n];
        let mut ans = 0;
        let s = s.as_bytes();

        for i in 1..n {
            for j in 0..i {
                if s[i] == s[j] {
                    f[i][j] = if j > 0 { f[i - 1][j - 1] + 1 } else { 1 };
                    ans = ans.max(f[i][j]);
                }
            }
        }
        ans
    }
}

Comments