Watch 10 video solutions for Longest Common Suffix Queries, a hard level problem involving Array, String, Trie. This walkthrough by codestorywithMIK has 6,860 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two arrays of strings wordsContainer and wordsQuery.
For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.
Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].
Example 1:
Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
Output: [1,1,1]
Explanation:
Let's look at each wordsQuery[i] separately:
wordsQuery[0] = "cd", strings from wordsContainer that share the longest common suffix "cd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.wordsQuery[1] = "bcd", strings from wordsContainer that share the longest common suffix "bcd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.wordsQuery[2] = "xyz", there is no string from wordsContainer that shares a common suffix. Hence the longest common suffix is "", that is shared with strings at index 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.Example 2:
Input: wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
Output: [2,0,2]
Explanation:
Let's look at each wordsQuery[i] separately:
wordsQuery[0] = "gh", strings from wordsContainer that share the longest common suffix "gh" are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.wordsQuery[1] = "acbfgh", only the string at index 0 shares the longest common suffix "fgh". Hence it is the answer, even though the string at index 2 is shorter.wordsQuery[2] = "acbfegh", strings from wordsContainer that share the longest common suffix "gh" are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.
Constraints:
1 <= wordsContainer.length, wordsQuery.length <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i] consists only of lowercase English letters.wordsQuery[i] consists only of lowercase English letters.wordsContainer[i].length is at most 5 * 105.wordsQuery[i].length is at most 5 * 105.Problem Overview: You receive two arrays of strings: wordsContainer and wordsQuery. For each query word, return the index of the container word sharing the longest common suffix. If multiple words share the same suffix length, choose the one with the shortest length, and if still tied, the smallest index.
The main challenge is efficiently comparing suffixes across many words. Direct comparisons work but become slow when both arrays are large. Reversing strings and using a Trie significantly reduces repeated comparisons.
Approach 1: Brute Force Suffix Comparison (O(Q * N * L) time, O(1) space)
For every query word, iterate through all words in wordsContainer. Compare characters from the end of both strings to compute the longest matching suffix. Track the best candidate using the rules: maximum suffix length, then minimum container word length, then smallest index. The comparison step costs up to O(L) per pair where L is the maximum string length. With Q queries and N container words, total complexity becomes O(Q * N * L). This approach is easy to implement but too slow for large inputs because it repeats suffix scans for every pair.
Approach 2: Trie on Reversed Strings (O(N * L + Q * L) time, O(N * L) space)
A more scalable approach uses a Trie. Since the problem focuses on suffixes, reverse every string in wordsContainer and insert it into the Trie character by character. While inserting, store at each node the index of the best candidate word according to the tie-breaking rules (shortest length, then smallest index). This ensures that every prefix of the reversed string already knows the optimal answer.
When processing a query, reverse it and traverse the Trie character by character. Each step corresponds to extending the suffix match. If traversal stops because a character path is missing, return the best index stored at the deepest node reached. Since traversal only follows the query length, each query costs O(L). Trie construction costs O(N * L). This reduces repeated comparisons and efficiently handles large datasets.
This approach relies on concepts from string processing and prefix trees commonly used for fast lookup problems involving shared prefixes or suffixes.
Recommended for interviews: Interviewers expect the Trie-based optimization. The brute force approach demonstrates understanding of suffix comparison and tie-breaking rules, but the optimized Trie solution shows the ability to transform a suffix problem into a prefix structure by reversing strings and caching the best candidate at each node.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Suffix Comparison | O(Q * N * L) | O(1) | Small input sizes or quick prototype implementations |
| Trie with Reversed Strings | O(N * L + Q * L) | O(N * L) | Large datasets with many queries requiring repeated suffix lookups |