Is Longest Repeating Substring easy or hard?

Longest Repeating Substring is generally considered a medium-level problem. The DP solution is straightforward once you recognize the longest common substring pattern, but optimized solutions using rolling hash or suffix arrays require stronger knowledge of string algorithms.

How to solve Longest Repeating Substring in O(n log n)?

Use binary search on the substring length combined with a rolling hash (Rabin–Karp). For each candidate length L, compute hashes for all substrings of length L and store them in a hash set. If a duplicate hash appears, a repeating substring exists. Binary search over the length range gives O(n log n) time.

What is the best approach for Longest Repeating Substring?

The most practical interview approach is dynamic programming with O(n^2) time and O(n^2) space. It compares all suffix pairs and tracks the longest common suffix length using a DP table. For better theoretical performance, binary search combined with rolling hash reduces the complexity to O(n log n).

What data structure is used in Longest Repeating Substring?

Common techniques rely on dynamic programming tables, hash sets for rolling hash comparisons, and advanced structures such as suffix arrays or LCP arrays. The choice depends on the desired time complexity and implementation difficulty.

What is the time complexity of Longest Repeating Substring?

The brute force method runs in O(n^3) time. A dynamic programming solution improves this to O(n^2) time with O(n^2) space. More advanced approaches such as binary search with rolling hash or suffix arrays can solve it in O(n log n) time.

Longest Repeating Substring Python or Java solution approach?

Most Python and Java solutions use a dynamic programming table where dp[i][j] stores the length of the common suffix ending at indices i and j. If characters match, extend the previous result with dp[i-1][j-1] + 1. The maximum value in the table is the answer, giving O(n^2) time complexity.

Is Longest Repeating Substring asked at Google, Amazon, or Meta?

Variants of longest repeating substring and longest duplicate substring problems appear in interviews at companies like Google, Amazon, and Meta. They are commonly used to test knowledge of string algorithms, hashing techniques, and suffix-based data structures.

Description Hints 2 Solution Video 43:45

1062. Longest Repeating Substring

Medium63.4% acceptance4 companiesPremium elsewhere, free here

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.

Asked at 4 companies

Coupang Amazon

Google Meta

Topics

Hints open one at a time

Hint 1

Generate all substrings in O(N^2) time with hashing.

Hint 2

Choose those hashing of strings with the largest length.

43:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"abcd"

Input

"abbaba"

Input

"aabcaabdaab"

Your code is saved on this device.Solution