Interview Guide: Suffix Arrays Problems and Solutions

What Is a Suffix Array?

A suffix array is a sorted list of all suffixes of a given string. Instead of storing the actual suffix strings, it stores the starting indices of those suffixes in lexicographical order. For a string of length n, there are exactly n suffixes. The suffix array gives us a compact, efficient way to access and process them in sorted order.

Consider the string "banana". Its suffixes are:

0: banana
1: anana
2: nana
3: ana
4: na
5: a

Sorted lexicographically, they become: "a", "ana", "anana", "banana", "na", "nana". The suffix array is the list of original indices in that order: [5, 3, 1, 0, 4, 2]. This compact representation unlocks many powerful string algorithms.

Why Suffix Arrays Matter in Technical Interviews

Suffix arrays appear frequently in coding interviews, especially at companies that value strong algorithmic foundations. They enable efficient solutions to many classic string problems that would otherwise require complex data structures like suffix trees. Key advantages:

• Pattern matching: find all occurrences of a substring in O(m log n) time, where m is the pattern length and n the text length.
• Longest repeated substring: find the longest substring that appears more than once.
• Longest common substring of two strings.
• Counting distinct substrings efficiently.
• Memory efficiency: suffix arrays use less memory than suffix trees, making them practical for large inputs.

Mastering suffix arrays demonstrates strong understanding of string algorithms, sorting, and binary search — all core interview competencies.

How to Construct a Suffix Array

There are multiple ways to build a suffix array, ranging from a naive O(n^2 log n) approach to linear-time algorithms. In interviews, the O(n log n) prefix-doubling method strikes the best balance between simplicity and efficiency. We'll cover both the naive and the efficient approach.

Naive Construction

The simplest method: generate all suffix strings, sort them using built-in string comparison, then extract the original indices. This is O(n^2 log n) due to the cost of comparing strings of average length n/2 during sorting.

def build_suffix_array_naive(s):
    n = len(s)
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort()  # each comparison can take O(n) time
    return [idx for _, idx in suffixes]

# Example
print(build_suffix_array_naive("banana"))  # [5, 3, 1, 0, 4, 2]

This works for small strings but will time out on large inputs. For interview purposes, you must know the optimized method.

Efficient O(n log n) Construction (Prefix Doubling)

The prefix-doubling algorithm sorts suffixes by their first 2^k characters, repeatedly doubling k until all suffixes are distinct. Each sorting step uses a pair of ranks (current rank of the suffix and the rank of the suffix starting at i+2^k), which can be compared in O(1).

Algorithm steps:

• Assign initial ranks based on the first character (e.g., ASCII value).
• Sort suffixes using pairs: (rank[i], rank[i+k]), where out-of-bounds indices get a sentinel value of -1.
• Reassign temporary ranks based on the new order, incrementing when the pair differs from the previous one.
• Double k and repeat until ranks are all distinct (max rank equals n-1).

def build_suffix_array(s):
    n = len(s)
    if n == 0:
        return []
    # initial ranks: character codes
    rank = [ord(c) for c in s]
    tmp = [0] * n
    sa = list(range(n))
    k = 1
    
    while True:
        # sort by (rank[i], rank[i+k]) with -1 for out-of-bounds
        sa.sort(key=lambda i: (rank[i], rank[i+k] if i+k < n else -1))
        
        # reassign temporary ranks
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev_idx = sa[i-1]
            curr_idx = sa[i]
            prev_pair = (rank[prev_idx], rank[prev_idx+k] if prev_idx+k < n else -1)
            curr_pair = (rank[curr_idx], rank[curr_idx+k] if curr_idx+k < n else -1)
            tmp[curr_idx] = tmp[prev_idx] + (1 if curr_pair != prev_pair else 0)
        
        # swap rank and tmp
        rank, tmp = tmp, rank
        
        # if all ranks are distinct, we are done
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    
    return sa

This implementation runs in O(n log n) time and O(n) extra space. The sentinel -1 ensures that shorter suffixes are sorted correctly when the prefix length exceeds their remaining characters.

Searching with a Suffix Array

Once we have the suffix array, finding all occurrences of a pattern P in the original string S becomes a simple binary search. We find the range of suffixes that start with P by locating the lower bound (first suffix ≥ P) and the upper bound (first suffix > P).

def search_pattern(s, sa, pattern):
    n = len(s)
    m = len(pattern)
    
    # lower bound: first index where suffix >= pattern
    low, high = 0, n
    while low < high:
        mid = (low + high) // 2
        # compare pattern with suffix starting at sa[mid]
        if s[sa[mid]:sa[mid]+m] < pattern:
            low = mid + 1
        else:
            high = mid
    left = low
    
    # upper bound: first index where suffix > pattern
    low, high = 0, n
    while low < high:
        mid = (low + high) // 2
        if s[sa[mid]:sa[mid]+m] <= pattern:
            low = mid + 1
        else:
            high = mid
    right = low
    
    # occurrences are sa[left:right]
    return left, right

# Example
s = "banana"
sa = build_suffix_array(s)
left, right = search_pattern(s, sa, "ana")
print(sa[left:right])  # indices of suffixes starting with "ana"

Each binary search step does a string slice comparison, which takes up to O(m) time. Thus the total time is O(m log n). In production code you'd avoid slicing and compare character-by-character, but for interviews the above is clear and acceptable.

The Longest Common Prefix (LCP) Array

The LCP array stores the lengths of the longest common prefixes between consecutive suffixes in the suffix array. It is essential for solving many problems like longest repeated substring or counting distinct substrings. The array can be built in O(n) time using Kasai's algorithm, which relies on the fact that the LCP of adjacent suffixes decreases by at most 1 when moving through the original string positions.

def build_lcp(s, sa):
    n = len(s)
    rank = [0] * n
    for i, idx in enumerate(sa):
        rank[idx] = i
    
    lcp = [0] * (n - 1)
    k = 0
    for i in range(n):
        r = rank[i]
        if r == n - 1:  # last suffix in SA, no next suffix to compare
            k = 0
            continue
        j = sa[r + 1]   # index of next suffix in SA
        # count matching characters from position k
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[r] = k
        if k > 0:
            k -= 1  # next iteration starts with at least k-1 matches
    return lcp

Now we have all the core tools: suffix array, pattern search, and LCP array. Let's apply them to common interview problems.

Common Interview Problems and Solutions

1. Pattern Matching (All Occurrences)

Given a text and a pattern, return all starting positions where the pattern appears. Using the suffix array and binary search as shown above, we can report the indices in O(m log n + occ) time, where occ is the number of occurrences.

2. Longest Repeated Substring

Find the longest substring that appears at least twice in the string. The answer is simply the maximum value in the LCP array; the substring starts at the position indicated by the suffix array.

def longest_repeated_substring(s):
    sa = build_suffix_array(s)
    lcp = build_lcp(s, sa)
    max_len = 0
    start = 0
    for i, length in enumerate(lcp):
        if length > max_len:
            max_len = length
            start = sa[i]
    return s[start:start+max_len] if max_len > 0 else ""

# Example
print(longest_repeated_substring("banana"))  # "ana"

3. Longest Common Substring of Two Strings

To find the longest substring that appears in both s1 and s2, we concatenate them with a separator that does not appear in either string (e.g., '#'). Then build the suffix array and LCP for the combined string. The longest common substring corresponds to the maximum LCP value where the two suffixes originate from different original strings.

def longest_common_substring(s1, s2):
    # use '#' as separator (assuming it doesn't appear in s1 or s2)
    combined = s1 + '#' + s2
    sa = build_suffix_array(combined)
    lcp = build_lcp(combined, sa)
    n1 = len(s1)
    max_len = 0
    start = 0
    for i in range(len(lcp)):
        idx1 = sa[i]
        idx2 = sa[i+1]
        # check that suffixes belong to different original strings
        if (idx1 < n1 and idx2 > n1) or (idx2 < n1 and idx1 > n1):
            if lcp[i] > max_len:
                max_len = lcp[i]
                start = min(idx1, idx2)  # start in combined string
    # extract the substring from s1 (or s2)
    return combined[start:start+max_len] if max_len > 0 else ""

# Example
print(longest_common_substring("ababc", "babca"))  # "babc"

4. Counting Distinct Substrings

The total number of substrings in a string of length n is n*(n+1)/2. Each repeated substring appears as a common prefix between consecutive suffixes in the suffix array. The LCP array tells us exactly how many prefixes are shared. The number of distinct substrings is therefore:

def count_distinct_substrings(s):
    n = len(s)
    sa = build_suffix_array(s)
    lcp = build_lcp(s, sa)
    total_substrings = n * (n + 1) // 2
    duplicate_count = sum(lcp)
    return total_substrings - duplicate_count

# Example
print(count_distinct_substrings("ababa"))  # 10

5. Lexicographically Smallest Suffix

The suffix array already gives us the answer: it's simply sa[0], the starting index of the first suffix in sorted order.

6. Finding All Distinct Substrings (Enumeration)

We can also list all distinct substrings by iterating over each suffix and skipping the first lcp[i] characters, because those were already seen in the previous suffix. This technique is useful when you need the actual substrings, not just the count.

Best Practices for Suffix Array Interview Solutions

• Know both naive and efficient construction: The naive version demonstrates understanding of the concept; the prefix-doubling version shows algorithmic maturity.
• Master binary search on suffix arrays: Practice writing the lower/upper bound logic until it becomes second nature.
• Understand the LCP array deeply: Its construction (Kasai's algorithm) and its applications are the key to solving harder problems.
• Handle edge cases explicitly: empty strings, strings with all identical characters, single-character strings, and when the pattern is longer than the text.
• Be precise with time and space complexity: Suffix array construction O(n log n), LCP O(n), searching O(m log n). Space O(n) for arrays.
• Use sentinels wisely: When combining strings, choose a separator that does not appear in the input. For LCP comparisons, ensure the separator prevents cross-string prefix matches.
• Practice writing clean, modular code: Separate functions for SA construction, LCP, search, and each problem. This makes your solution easier to explain and debug.
• Don't rely on external libraries: Show you can implement the core logic from scratch; avoid using sorted with custom keys that hide the ranking logic unless you explicitly explain it.

Conclusion

Suffix arrays are a versatile and interview-relevant data structure that unlocks efficient solutions to a wide family of string problems. By building a solid understanding of their construction, the accompanying LCP array, and binary search techniques, you can confidently tackle challenges like pattern matching, longest repeated substrings, common substrings between strings, and distinct substring counting. Implement the algorithms from scratch, test with varied inputs, and internalize the prefix-doubling logic — this preparation will serve you well in any technical interview that delves into advanced string processing.