Suffix Array and LCP Array (Intro)

This is an extension topic beyond most interviews; it pays off in hard substring questions (longest repeated substring, distinct substrings, longest common substring) where you want a deterministic O(n log n)-ish answer instead of hashing.

Intuition

Write down every suffix of s and sort them lexicographically. The suffix array sa lists their starting positions in that order. For s = "banana":

rank	start	suffix
0	5	a
1	3	ana
2	1	anana
3	0	banana
4	4	na
5	2	nana

Every substring is a prefix of some suffix, and in sorted order, suffixes that share a long prefix sit next to each other. So the LCP array, lcp[i] = longest common prefix of the suffixes at ranks i - 1 and i, captures all repetition in the string: here [0, 1, 3, 0, 0, 2]. The longest repeated substring is "ana", from the largest LCP value.

Building it (prefix doubling). Sort suffixes by their first character. If you know the order by the first k characters (as ranks), the order by the first 2k characters is just sorting by the pair (rank[i], rank[i + k]), because the first 2k characters of suffix i are the first k of i followed by the first k of i + k. After about log n rounds all ranks are distinct and you are done.

LCP in linear time (Kasai). Visit suffixes in text order i = 0, 1, 2, .... If suffix i shares h characters with its sorted predecessor, then suffix i + 1 shares at least h - 1 with its own predecessor (drop the first character of both). So h only decreases by one per step, and the total work is O(n).

When to use it in interviews / OAs

• Longest substring that occurs at least twice (or at least k times: a window of k - 1 LCP values).
• Number of distinct substrings: n(n + 1)/2 - sum(lcp).
• Longest common substring of two strings: join them with a unique separator and look at neighbouring suffixes from different strings.
• Lexicographic questions: the k-th smallest distinct substring, the lexicographically last substring (it is simply the largest suffix).
• When hashing feels risky (adversarial tests) or you need many different substring comparisons.

Template

Suffix array by prefix doubling

def suffix_array(s: str) -> list[int]:
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while n:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)  # -1: shorter suffix first
        sa.sort(key=key)
        new_rank = [0] * n
        for idx in range(1, n):
            new_rank[sa[idx]] = new_rank[sa[idx - 1]] + (key(sa[idx]) != key(sa[idx - 1]))
        rank = new_rank
        if rank[sa[-1]] == n - 1:  # all ranks distinct: fully sorted
            break
        k *= 2
    return sa

LCP array (Kasai)

def lcp_array(s: str, sa: list[int]) -> list[int]:
    # lcp[i] = longest common prefix of suffixes sa[i - 1] and sa[i]; lcp[0] = 0
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp = [0] * n
    h = 0
    for i in range(n):  # text order: h drops by at most one per step
        if rank[i] == 0:
            h = 0
            continue
        j = sa[rank[i] - 1]  # the suffix just before suffix i in sorted order
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[rank[i]] = h
        if h:
            h -= 1
    return lcp

Applications

def count_distinct_substrings(s: str) -> int:
    n = len(s)
    return n * (n + 1) // 2 - sum(lcp_array(s, suffix_array(s)))  # each LCP counts repeats


def longest_repeated_substring(s: str) -> str:
    if not s:
        return ""
    sa = suffix_array(s)
    lcp = lcp_array(s, sa)
    i = max(range(len(s)), key=lcp.__getitem__)
    return s[sa[i]:sa[i] + lcp[i]]


def longest_common_substring(a: str, b: str) -> str:
    s = a + "\x00" + b  # unique separator: no common prefix can cross it
    sa = suffix_array(s)
    lcp = lcp_array(s, sa)
    best, pos = 0, 0
    for i in range(1, len(s)):
        if (sa[i] < len(a)) != (sa[i - 1] < len(a)) and lcp[i] > best:  # neighbours from different strings
            best, pos = lcp[i], sa[i]
    return s[pos:pos + best]

Complexity

The doubling version does at most log n rounds, each a comparison sort: O(n log^2 n) time, O(n) memory. Replacing the sort with two counting-sort passes gives O(n log n), and specialized algorithms (SA-IS, DC3) reach O(n); both are beyond interview scope. Kasai's LCP is O(n). In Python, this simple version builds both arrays for 10^5 characters in well under a second on a laptop.

Common pitfalls

• Sorting the suffix strings directly (sorted(range(n), key=lambda i: s[i:])) builds O(n^2) characters of slices. Fine as a brute-force check, not as the solution.
• The out-of-range rank. A suffix that ends before i + k must sort before longer ones with the same prefix; use a value smaller than every real rank (here -1).
• Stopping too early or too late. Stop when all ranks are distinct, not after a fixed number of rounds.
• LCP indexing conventions. Some definitions pair sa[i] with sa[i + 1]; be consistent when you scan windows.
• Separators. For two or more strings, separators must be unique and absent from the inputs; otherwise a common prefix can run across the boundary.
• Lazy closures. In Python, define the sort key after updating rank and k for the round (as above), or the key reads stale values.

Interview variations

• Longest duplicate substring. longest_repeated_substring; rolling hash plus binary search is the other common solution.
• Repeated at least k times. The maximum over windows of k - 1 consecutive LCP values of their minimum (a sliding-window minimum).
• Distinct substrings / distinct echo substrings. Count with the LCP sum, or enumerate by rank.
• Longest common substring of m strings. Concatenate with distinct separators, then find the best window of sorted suffixes covering all m sources (two pointers plus a monotonic deque).
• Last substring in lexicographical order. s[sa[-1]:]; an O(n) two-pointer method also exists.
• Comparing any two substrings. With rank and LCP plus a range-minimum structure, LCP of arbitrary suffixes is O(1); a sparse table is the usual partner.