Longest Common Suffix Queries

Longest Common Suffix Queries

What is this problem about?

The Longest Common Suffix Queries problem provides you with two arrays of strings: a wordsContainer array and a wordsQuery array. For each query string, you must find a string in the wordsContainer that shares the longest common suffix with the query. If there's a tie (multiple words share the same longest suffix), you must pick the shortest word among them. If there is still a tie, you pick the one that appeared first in the container array.

Why is this asked in interviews?

This problem is heavily favored by companies dealing with search engines, autocomplete features, or large text databases. It is a fantastic test of a candidate's ability to implement and customize advanced data structures. It evaluates whether you can reverse a string problem to fit standard prefix-matching tools and how well you can manage multiple variables (length, original index) at a granular node level.

Algorithmic pattern used

The definitive pattern for this problem is the Trie (Prefix Tree). However, because we are looking for a suffix, we must first reverse all the strings in both the container and the query. As we insert the reversed container words into the Trie, we store metadata at every node: specifically, the index of the best string (shortest length, earliest occurrence) that passes through that node. This makes querying incredibly fast.

Example explanation

Let wordsContainer = ["apple", "maple", "pineapple"]. Queries: ["sample", "grapple"]. First, reverse the container: ["elppa", "elpam", "elppaenip"]. We insert these into a Trie. The root node, and the nodes for e-l-p will be shared. When inserting "elppa" (apple, len 5, idx 0), the e-l-p nodes record index 0. When inserting "elpam" (maple, len 5, idx 1), it branches at 'a'. When inserting "elppaenip" (pineapple, len 9, idx 2), it shares e-l-p-p-a. Since "apple" (idx 0) is shorter than "pineapple" (idx 2), the nodes e-l-p-p-a keep index 0 as their "best" match. Query "sample" reverses to "elpmas". We traverse the Trie: e -> l -> p. Next is m. The Trie has m (from maple), so we go there. End of match. The node m stored index 1. So "maple" is the answer!

Common mistakes candidates make

A common error is trying to compare suffixes using brute force loops ($O(Q \times N \times L)$). This will easily trigger a Time Limit Exceeded error. Another frequent mistake is properly building the Trie but failing to update the "best index" metadata as you traverse down the nodes during insertion. You must evaluate the tie-breaking rules (length, then index) at every single character node you create or visit.

Interview preparation tip

To excel at the Longest Common Suffix Queries coding problem, practice building Tries where nodes contain more than just child pointers and a boolean isEnd flag. Get comfortable injecting metadata (like min-length or original string index) into your Trie nodes so that you can retrieve precomputed answers instantly during the query phase.