How Longest Repeated Substring Works: Step-by-Step

1. Introduction and Core Concepts

The longest repeated substring is one of the most fundamental problems in string algorithms, asking a deceptively simple question: given a string, what is the longest substring that appears at least twice? Unlike the longest common substring between two different strings, this problem searches for repetition within a single string, allowing overlaps unless explicitly forbidden. For example, in the string "banana", the longest repeated substring is "ana", which occurs at positions 1 and 3, overlapping by one character.

Understanding the longest repeated substring is essential because repetition is a core signal in data. Repetition indicates redundancy, structure, and compressibility. From detecting duplicated code in a large codebase to identifying repeated motifs in DNA sequences, the ability to find the longest repeated pattern efficiently underpins compression, bioinformatics, plagiarism detection, and data deduplication. The problem also serves as a gateway to more advanced data structures such as suffix arrays, suffix trees, and suffix automata.

Formally, given a string S of length n over an alphabet Σ, a substring S[i..i+L-1] is repeated if there exists another index j != i such that S[i..i+L-1] = S[j..j+L-1]. The longest repeated substring is the repeated substring with maximum L. If multiple substrings tie for maximum length, any one may be returned, or all can be enumerated. Two important variants exist: the overlapping variant, which allows j < i+L, and the non-overlapping variant, which requires |i - j| >= L. The choice of variant dramatically affects both the algorithm and the result. For "aaaa", the overlapping longest repeated substring is "aaa", while the non-overlapping version is "aa".

Why It Matters Beyond Theory

Naively, finding the longest repeated substring seems trivial to brute-force, but the combinatorial explosion of substrings makes efficiency critical. A string of length n has n(n+1)/2 substrings, and comparing them pairwise is infeasible for large n. Modern datasets routinely contain millions or billions of characters — genomes, log files, or web crawls — so linear or near-linear algorithms are not just academic exercises but practical necessities.

The problem also illustrates a key algorithmic principle: transforming a string problem into a sorting problem. By sorting all suffixes of the string, repeated substrings become adjacent in sorted order, reducing the search to a linear scan of neighboring suffixes. This insight connects stringology to classic sorting and array algorithms, making it a favorite for teaching advanced data structures.

2. How It Works

The most efficient and widely taught approach to the longest repeated substring relies on two complementary structures: the suffix array and the Longest Common Prefix (LCP) array. A suffix array SA is a permutation of indices 0..n-1 such that the suffixes S[SA[0]..], S[SA[1]..], ..., S[SA[n-1]..] are lexicographically sorted. Once suffixes are sorted, any repeated substring must be a common prefix of at least two suffixes, and the longest such prefix will necessarily appear between two suffixes that are adjacent in the sorted order.

The LCP array stores exactly that information. LCP[i] is defined as the length of the longest common prefix between the suffixes starting at SA[i] and SA[i+1]. For a string of length n, the LCP array has length n-1. The maximum value in the LCP array is precisely the length of the longest repeated substring, and the substring itself can be recovered by taking the prefix of length max(LCP) from either of the two corresponding suffixes. This reduces the problem to building SA and LCP efficiently.

Building the suffix array can be done in O(n log n) with the classic prefix-doubling method, or in O(n) with advanced algorithms like SA-IS or DC3. The LCP array is then built in O(n) time using Kasai's algorithm, which exploits the fact that LCP values between consecutive ranks can be computed incrementally without re-scanning characters from scratch. Together, they yield an O(n log n) solution that is both practical and easy to implement.

The Core Intuition

Consider why adjacency in the suffix array is sufficient. If a substring R appears at positions i and j, then both suffixes S[i..] and S[j..] start with R. In sorted order, all suffixes starting with R will occupy a contiguous interval. Therefore, the two occurrences of R will be somewhere inside that interval, and the minimum LCP value across that interval is at least |R|. The maximum LCP overall must therefore be at least as large as the longest repeated substring, and cannot be larger because any common prefix of two suffixes is by definition a repeated substring.

Alternative theoretical models achieve the same result using suffix trees or suffix automata. A suffix tree is a compressed trie of all suffixes where each internal node corresponds to a repeated substring, and the deepest internal node gives the answer. A suffix automaton, the minimal deterministic automaton recognizing all substrings, encodes repetitions in its states with occurrence counts. While these structures offer linear-time guarantees, suffix arrays are often preferred in practice due to their smaller memory footprint and simpler implementation.

Overlapping vs. Non-Overlapping

The standard suffix array + LCP method naturally finds overlapping repetitions because it only cares about prefix equality, not distance between occurrences. To enforce non-overlapping, we must add a constraint: for a candidate length L derived from LCP[i] between suffixes at SA[i] and SA[i+1], we check if |SA[i] - SA[i+1]| >= L. If not, the candidate is invalid for the non-overlapping variant, and we must consider the next best LCP value. This variant is common in data compression and plagiarism detection where overlapping copies are not useful.

3. Implementation

Implementing the longest repeated substring efficiently in Python requires careful handling of suffix sorting and LCP computation. Below are four progressive implementations, from the naive baseline to the optimized suffix array solution. Note that all code blocks escape HTML-sensitive characters for safe rendering.

The naive approach is useful for understanding the problem and for very small strings, but it quickly becomes impractical. The optimized approach uses prefix-doubling for the suffix array and Kasai's algorithm for the LCP array, achieving O(n log n) time with pure Python.

Naive Brute-Force Baseline

def longest_repeated_substring_naive(s):
    """Brute-force O(n^3) solution for longest repeated substring.
    Compares every pair of suffixes character by character.
    Suitable only for n < 200.
    """
    n = len(s)
    longest = ""
    # Compare every pair of starting positions
    for i in range(n):
        for j in range(i + 1, n):
            k = 0
            # Extend while characters match
            while j + k < n and i + k < n and s[i + k] == s[j + k]:
                k += 1
                # Update best if we found longer repetition
                if k > len(longest):
                    longest = s[i:i + k]
    return longest

# Example
print(longest_repeated_substring_naive("banana"))  # -> "ana"
print(longest_repeated_substring_naive("abcd"))    # -> ""

Building the Suffix Array with Prefix Doubling

def build_suffix_array(s):
    """Build suffix array using prefix-doubling in O(n log n).
    Returns list SA where SA[i] is start index of i-th smallest suffix.
    """
    n = len(s)
    if n == 0:
        return []
    # Initial rank is character code
    rank = [ord(c) for c in s]
    sa = list(range(n))
    tmp = [0] * n
    k = 1
    while True:
        # Sort by (rank[i], rank[i+k]) tuple
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev, cur = sa[i-1], sa[i]
            prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1)
            # Increase rank if keys differ
            tmp[cur] = tmp[prev] + (prev_key < cur_key)
        rank, tmp = tmp, rank
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1  # Double the prefix length
    return sa

Building the LCP Array with Kasai's Algorithm

def build_lcp_array(s, sa):
    """Kasai's algorithm to build LCP array in O(n).
    LCP[i] = longest common prefix of suffixes SA[i] and SA[i+1].
    """
    n = len(s)
    if n <= 1:
        return []
    rank = [0] * n
    for i, suffix_idx in enumerate(sa):
        rank[suffix_idx] = i
    lcp = [0] * (n - 1)
    h = 0  # Current LCP length
    for i in range(n):
        r = rank[i]
        if r == 0:
            continue  # First suffix has no predecessor
        j = sa[r - 1]
        # Extend h as far as characters match
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[r - 1] = h
        if h > 0:
            h -= 1  # Decrease for next iteration (key optimization)
    return lcp

Complete Optimized Solution

def longest_repeated_substring(s):
    """Find longest repeated substring using suffix array + LCP.
    Time: O(n log n), Space: O(n). Allows overlapping occurrences.
    """
    if not s or len(s) < 2:
        return ""
    sa = build_suffix_array(s)
    lcp = build_lcp_array(s, sa)
    if not lcp:
        return ""
    max_len = max(lcp)
    if max_len == 0:
        return ""  # No repeated substring
    # Retrieve substring from suffix array
    max_idx = lcp.index(max_len)
    start = sa[max_idx]
    return s[start:start + max_len]

def longest_repeated_non_overlapping(s):
    """Variant that forbids overlapping occurrences."""
    if len(s) < 2:
        return ""
    sa = build_suffix_array(s)
    lcp = build_lcp_array(s, sa)
    best = ""
    best_len = 0
    for i, length in enumerate(lcp):
        if length <= best_len:
            continue
        pos1, pos2 = sa[i], sa[i+1]
        # Check non-overlapping constraint
        if abs(pos1 - pos2) >= length:
            best_len = length
            best = s[pos1:pos1 + length]
        else:
            # Even if overlapping, a shorter prefix may be valid
            # The valid length is limited by distance
            valid_len = abs(pos1 - pos2)
            # But we need to ensure prefix of that length still matches
            # Since LCP is >= valid_len, prefix of length valid_len matches
            if valid_len > best_len:
                best_len = valid_len
                best = s[pos1:pos1 + valid_len]
    return best

# Tests
print(longest_repeated_substring("banana"))      # "ana"
print(longest_repeated_substring("aaaa"))        # "aaa" (overlapping)
print(longest_repeated_non_overlapping("aaaa"))  # "aa" (non-overlapping)
print(longest_repeated_substring("abcpqrabcxyz")) # "abc"

4. Step-by-Step Example

Let us walk through the complete algorithm for the classic example S = "banana" (n=6). This example is illustrative because it contains an overlapping repetition and demonstrates how sorting groups similar suffixes together.

First, we enumerate all suffixes with their starting indices: 0:"banana", 1:"anana", 2:"nana", 3:"ana", 4:"na", 5:"a". Sorting these lexicographically yields the suffix array. Lexicographic order compares character by character: "a" < "ana" < "anana" < "banana" < "na" < "nana".

Thus, SA = [5, 3, 1, 0, 4, 2]. We can verify: suffix 5 is "a", suffix 3 is "ana", suffix 1 is "anana", suffix 0 is "banana", suffix 4 is "na", suffix 2 is "nana". This sorted order is the backbone of the method.

Computing LCP Values

Next, we compute LCP between each adjacent pair in SA. We compare suffixes pairwise: LCP between SA[0]=5 ("a") and SA[1]=3 ("ana") is 1 ("a"). Between SA[1]=3 ("ana") and SA[2]=1 ("anana") is 3 ("ana"). Between SA[2]=1 ("anana") and SA[3]=0 ("banana") is 0. Between SA[3]=0 ("banana") and SA[4]=4 ("na") is 0. Between SA[4]=4 ("na") and SA[5]=2 ("nana") is 2 ("na"). So LCP = [1, 3, 0, 0, 2].

The maximum LCP value is 3 at index 1, corresponding to suffixes starting at 3 ("ana") and 1 ("anana"). The prefix of length 3 from either suffix is "ana", which is the longest repeated substring. Note that the two occurrences overlap in the original string: "banana" and "banana", sharing the 'a' at position 3, but the algorithm correctly identifies it.

Visual Trace Table

To make the process concrete, the following table shows the sorted suffixes alongside their LCP values. Scanning the LCP column for the maximum immediately reveals the answer without exhaustive substring enumeration.

This walkthrough highlights why the suffix array approach is so powerful: after an O(n log n) sort, the answer is found in a single linear scan. For longer strings like "abracadabra", the same process yields SA sorted suffixes and LCP maximum 4 for "abra", which appears at positions 0 and 7.

5. Complexity Analysis

Complexity analysis for the longest repeated substring depends heavily on the chosen implementation. The naive method is simple but exponential in practice, while suffix-based methods trade implementation complexity for near-linear performance. Understanding these trade-offs is critical when selecting an algorithm for production workloads.

The naive brute-force approach compares all O(n^2) substring pairs and each comparison can take O(n) time in the worst case, leading to O(n^3) time overall. Even with early termination, it remains O(n^2) on average and uses O(1) extra space besides the result. It is only viable for n < 500.

The suffix array with prefix-doubling runs in O(n log n) time due to log n sorting iterations, each O(n log n) for the sort, and O(n) space for SA, rank, and LCP arrays. With a linear-time suffix array construction algorithm such as SA-IS or DC3, the total time drops to O(n). Kasai's LCP construction is always O(n) time and O(n) space. Suffix tree and suffix automaton approaches also achieve O(n) time but with higher constant factors and larger memory overhead due to tree nodes and edges.

In practice, the O(n log n) prefix-doubling suffix array is the sweet spot for most Python applications: it is fast enough for strings up to hundreds of thousands of characters and is far simpler to implement correctly than linear-time alternatives. For truly massive inputs, such as genomic data with n > 10^7, a library implemented in C using SA-IS or a suffix automaton is preferable. Memory usage is also a consideration: storing the suffix array as integers requires 4n or 8n bytes, while a suffix tree can require 20n bytes or more due to node objects and edge dictionaries.

6. Variations and Optimizations

The basic longest repeated substring problem admits several important variations that tailor the solution to specific constraints. Recognizing these variants helps avoid applying the wrong algorithm to a nuanced requirement.

The longest repeated non-overlapping substring variant is common in compression where overlapping copies cannot be used for dictionary replacement. As described earlier, this requires filtering LCP candidates by the distance between suffix positions. A related variant asks for the longest substring that appears at least k times, not just twice. This generalizes the LCP scan: the answer is the maximum over all windows of k-1 consecutive LCP values of the minimum LCP inside the window. A sliding window minimum with a deque solves this in O(n).

Another variant seeks the longest repeated substring that is also a palindrome or that satisfies additional character constraints. These can be solved by combining suffix array techniques with palindromic tree structures or by filtering candidates post hoc. For the case where we need all longest repeated substrings (when ties exist), we simply collect all LCP indices where LCP == max(LCP) instead of taking the first.

Key Optimizations

Several optimizations improve real-world performance. First, using Python's built-in Timsort with key functions is faster than manual comparison loops for moderate n, but for large n, using the doubling method with integer ranks and counting sort (radix sort) reduces the sorting cost from O(n log n) to O(n) per iteration. Second, Kasai's algorithm already contains the crucial optimization of reusing the previous h value, avoiding O(n^2) rescanning.

For binary alphabets or small alphabets like DNA (A,C,G,T), specialized suffix array construction using induced sorting is dramatically faster. For general text, using library implementations such as pydivsufsort or implementing suffix array in PyPy with array('i') can yield 10x speedups over pure Python.

Rolling hash with binary search offers an alternative optimization that is often easier to code under interview pressure. The idea is to binary search the answer length L and check if any substring of length L repeats using a hash set of rolling hashes (e.g., Rabin-Karp). This runs in O(n log n) expected time and uses O(n) space, and while it has a small probability of hash collision, double hashing makes it negligible. It is particularly useful when only the length is needed, not the substring itself.

7. Real-World Applications

Although the longest repeated substring sounds like a purely academic problem, it appears surprisingly often in systems that handle large-scale string data. Its ability to identify redundancy and structure makes it valuable across domains.

In bioinformatics, genomes contain massive repeated regions such as transposons, tandem repeats, and duplicated genes. Finding the longest repeated substring in a chromosome helps identify these biologically significant repeats, which are linked to genetic diseases and evolutionary analysis. Tools for genome assembly use repeated substring detection to resolve ambiguous overlaps between reads.

In data compression, algorithms like LZ77 and LZ78 work by replacing repeated substrings with references to earlier occurrences. The longest repeated substring directly determines the maximum achievable compression ratio for a given window. Similarly, in data deduplication for backup systems and cloud storage, identifying long repeated chunks across files allows storing only one copy and replacing duplicates with pointers, saving terabytes of storage.

Web servers, databases, and networks also benefit. Log analysis often searches for repeated request patterns or error message templates to detect anomalies or attacks. In databases, finding repeated substrings in query logs helps with query caching and materialized view selection. Plagiarism detection systems use repeated substring analysis to find longest common passages between documents, while code clone detection in software engineering identifies duplicated code blocks for refactoring.

Even in networking, packet payload inspection for intrusion detection systems looks for repeated byte sequences that match known worm signatures. The efficiency of suffix array methods allows these systems to scan gigabit streams in near real time when implemented in optimized C or hardware.

8. Comparison with Alternatives

The longest repeated substring is closely related to several other string problems, and choosing the right tool depends on the exact question being asked. Confusing these problems is a common source of errors in interviews and system design.

The longest common substring between two strings finds the longest substring shared by both strings, typically solved with a generalized suffix array or dynamic programming. The longest repeated substring is a special case where the two strings are the same, but the algorithms differ in handling the diagonal. The longest palindromic substring seeks the longest substring that reads the same forwards and backwards, solved with Manacher's algorithm, and is unrelated to repetition. The longest repeated subsequence allows non-contiguous characters, which is a completely different problem solved with LCS dynamic programming.

Within the repeated substring family, the choice of data structure matters. Suffix arrays are memory-efficient and cache-friendly, suffix trees are theoretically optimal but heavy, suffix automata are elegant for counting occurrences, and rolling hash methods are simple but probabilistic. The table below summarizes these trade-offs.

For most practical Python work, suffix array + LCP offers the best balance of performance and implementability. If you need to answer many queries about different repetition thresholds or want to enumerate all repeated substrings, building a suffix automaton once and querying it repeatedly is more efficient. If you are in a coding interview with limited time, the rolling hash + binary search approach is the fastest to write correctly and passes most test cases.

9. Common Mistakes and Best Practices

Even experienced developers make subtle mistakes when implementing longest repeated substring solutions. Awareness of these pitfalls saves hours of debugging and ensures correctness on edge cases.

A frequent mistake is forgetting that Python's default string sorting of suffixes via sorted(s[i:] for i in range(n)) creates O(n^2) memory by copying suffixes, which fails for n > 5000 due to memory and time blowup. Always sort indices with a key or rank array rather than materializing suffix strings. Another common error is off-by-one handling in the LCP array: LCP has length n-1, and accessing LCP[n-1] or SA[n] causes index errors. Careful bounds checking in Kasai's loop is essential.

Overlapping versus non-overlapping confusion is another pitfall. Many solutions correctly return "aaa" for "aaaa" when the problem statement expected non-overlapping "aa". Always clarify the requirement with the interviewer or specification. Similarly, returning the length instead of the substring, or returning only one of multiple equally long answers without documenting the tie-breaking behavior, can cause test failures.

Hash-based solutions often neglect collision handling. Using a single 32-bit modulus is unsafe for large inputs; use Python's built-in hash with double modulus (e.g., 10**9+7 and 10**9+9) or use a deterministic method for final verification by direct string comparison when a hash match is found.

Best Practices

• Validate edge cases first: Test with "", "a", "aa", "ab", "aaaa", and "banana" before scaling. Ensure empty and single-character strings return "".
• Use Kasai correctly: Initialize h = 0 and decrement h by 1 after each iteration if h > 0. This reuse is what guarantees O(n) time.
• Prefer iterative doubling with radix sort: For n > 10^5, replace Python's Timsort key with counting sort on ranks to avoid O(n log^2 n) behavior.
• Profile memory: Store SA and rank as arrays of ints using Python lists or array('i'); avoid storing suffix strings.
• Document variant: Clearly state in function docstrings whether overlapping is allowed and whether the function returns the substring, its length, or all candidates.
• Test non-overlapping separately: Write a dedicated test suite that checks distance constraints, e.g., assert longest_repeated_non_overlapping("aaaa") == "aa".
• Consider library use: In production, prefer battle-tested libraries like divsufsort or libsais via Python bindings instead of pure Python for gigabyte-scale inputs.

Finally, always escape HTML and handle Unicode correctly if the input may contain non-ASCII characters. Python's ord(c) works for Unicode, but sorting behavior depends on code points; for locale-aware sorting, additional normalization may be needed.

10. Interview Questions

The longest repeated substring is a staple of technical interviews for roles involving algorithms, data engineering, and bioinformatics. Interviewers use it to assess understanding of suffix structures, sorting, and complexity analysis. Below are common questions with concise answer strategies.

Q1: Find the longest repeated substring in "abracadabra". What is the answer and how would you find it efficiently?

Answer: The longest repeated substring is "abra" (appears at 0 and 7) with length 4. The efficient approach is to build the suffix array for "abracadabra", compute the LCP array, and take the maximum LCP value. Naive O(n^3) is too slow for follow-up constraints. Be prepared to walk through suffix sorting manually for a small example and explain why adjacent suffixes in SA suffice. Mention time O(n log n) and space O(n).

Q2: How would you modify your solution to find the longest substring that appears at least k times?

Answer: Generalize the LCP scan. After building SA and LCP, the longest substring appearing at least k times corresponds to the maximum of the minimum LCP over every window of k-1 consecutive LCP entries. Use a deque to maintain sliding window minimum in O(n). For example, with k=3 and S="banana", the windows of size 2 are [1,3] min=1, [3,0] min=0, etc., so the answer is "a" appearing 3 times. Explain the connection to finding k suffixes sharing a common prefix.

Q3: What is the difference between longest repeated substring and longest repeated subsequence? Can you solve the latter with suffix arrays?

Answer: Substring requires contiguity, subsequence does not. "abcde" has repeated subsequence "ace" is not a substring. Suffix arrays do not help for subsequence, which is solved via dynamic programming for Longest Common Subsequence between the string and itself with the constraint i != j, or more generally via DP. The subsequence version is NP-hard for multiple strings but O(n^2) for two. This question tests precise definitions.

Q4: How do you handle non-overlapping constraint? Give an example where overlapping matters.

Answer: For S="aaaa", overlapping longest is "aaa" (positions 0 and 1 overlap), non-overlapping is "aa" (positions 0 and 2). To enforce non-overlapping, after computing LCP[i] between SA[i] and SA[i+1], check if |SA[i] - SA[i+1]| >= LCP[i]. If not, the valid length is limited to the distance. Some solutions binary search length and check hash sets with position filtering. Discuss trade-offs and provide code for the filtered scan.

Q5: Can you solve longest repeated substring using binary search and rolling hash? What are the pros and cons?

Answer: Yes. Binary search the length L between 1 and n//2 (or n-1 for overlapping). For each mid, compute rolling hashes of all substrings of length mid in O(n) and check for duplicate hash in a set. If duplicate exists, search higher; else lower. Pros: easy to implement quickly, O(n log n) expected, low code complexity. Cons: probabilistic due to collisions (mitigate with double hashing and verification), not deterministic, and requires O(n) extra space for hash set. It is often the fastest interview solution to code correctly under time pressure.

Mastering these questions demonstrates not just the ability to code the algorithm, but to reason about variants, complexity, and practical engineering trade-offs — exactly what interviewers look for in senior candidates.