Suffix Array Coding Problems: 1 Question with Solutions

How suffix array works, step by step

1. A suffix array lists where each suffix of a string starts, in sorted order. "banana" has 6 suffixes; comparing whole suffixes costs up to O(n) per comparison, so instead they are ranked by prefixes of 1, 2, 4, … characters.
2. Rank by the first character alone: 'a' gets 0, 'b' gets 1 and 'n' gets 2. Ties remain within "a" (suffixes 1, 3 and 5) and "n" (suffixes 2 and 4), so they need a longer look.
3. Double to 2 characters without reading them: suffix i's key is (rank of i, rank of i + 1), two ranks already known, with − for past the end. The pairs break some ties, but "an" (suffixes 1 and 3) and "na" (suffixes 2 and 4) still need a longer look.
4. Double again to 4 characters with the pair (rank of i, rank of i + 2). Now all 6 ranks differ, so the order is final: the suffix array is [5, 3, 1, 0, 4, 2].
5. Neighbours in sorted order share prefixes: the LCP array [−, 1, 3, 0, 0, 2] is each suffix's common prefix with the one above. Since every repeated substring is such a shared prefix, "banana" has 21 − 6 = 15 distinct substrings.
6. Every suffix that starts with "ana" sits in one block of the sorted order, so two binary searches find its edges: the block holds suffixes 3 and 1. "ana" occurs at 1 and 3, found in O(m log n).
7. The suffix array of "banana" is [5, 3, 1, 0, 4, 2]. Prefix doubling needed 3 sorting rounds, one per doubling of the compared length (1, 2, 4), so it costs O(n log² n) with a comparison sort or O(n log n) with radix sort; the LCP array follows in O(n).

Suffix Array study plan

The one Suffix Array problem (1 hard) over 1 day, about 1 h 5 min in all — the pattern first, then easiest to hardest. Then move on to Segment Tree.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Number of Ways to Separate Numbers Hard

Next topic: Segment Tree

Suffix Array: the essentials

When to reach for it

Many questions about one string's substrings: the longest one that repeats, how many are distinct, the longest common substring of two strings, or comparing two substrings over and over inside a loop. Sorted suffixes put each substring beside its other occurrences.

The pattern

The suffix array lists the suffix starts in sorted order; its inverse, rank[i], says where suffix i landed. Prefix doubling sorts by the first 1, 2, 4, 8 … characters, each round sorting pairs of the previous ranks. Kasai's algorithm then fills the LCP array, the common prefix of each pair of neighbours, in O(n). Equal-length substrings at i and j are equal when their suffixes' LCP reaches the length, and otherwise ordered as rank[i] and rank[j]. For a few thousand characters, lcp[i][j] = lcp[i + 1][j + 1] + 1 when s[i] == s[j] does the same with less code.

def suffix_array(s):                # starts of the suffixes, in sorted order
    n, k = len(s), 1
    rank, sa = [ord(c) for c in s], list(range(n))
    while True:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)            # by the first 2k characters
        new = [0] * n
        for a, b in zip(sa, sa[1:]):
            new[b] = new[a] + (key(a) != key(b))
        rank, k = new, 2 * k
        if not n or rank[sa[-1]] == n - 1:  # every rank distinct: sorted
            return sa

Cost

Prefix doubling with a comparison sort is O(n log² n); radix-sorting the pairs gives O(n log n), and SA-IS O(n). Kasai is O(n). Space is O(n), against O(n²) for the quadratic table.

Common mistakes

• Sorting the suffixes as strings, sorted(range(n), key=lambda i: s[i:]), which copies O(n²) characters.
• Ranking a suffix that has run out of characters after one that continues; the empty remainder sorts first — the -1 in the key.
• Reading the LCP of two arbitrary suffixes from one entry; it is the LCP array's minimum between their ranks.
• Stopping the doubling after a fixed number of rounds, not when every rank is distinct.

Start with

• Number of Ways to Separate Numbers: an O(1) comparison of equal-length substrings inside a dynamic programming table.

All suffix array problems

Hard (1)

• Number of Ways to Separate Numbers String, Dynamic Programming, Prefix Sum

Companies that ask suffix array problems

• Amazon 1 problem on suffix array
• Google 1 problem on suffix array
• Meta 1 problem on suffix array

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems