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.
This approach involves reversing both the wordsContainer and wordsQuery strings. By doing so, the problem of finding the longest common suffix is converted into finding the longest common prefix, which can be done directly by comparing characters sequentially. For each query word, check all words in the container and determine which word provides the longest common prefix when reversed. Handle ties by choosing the shortest word or the earliest occurring one.
We reverse the process to determine the longest common suffix by iterating backward from the end of both words. This checks character-by-character equality from the word-ending towards the start. The function longestCommonSuffixLength calculates this common length, while findBestMatch selects the best matching word based on the described criteria.
Time Complexity: O(n * m * k), where n is the number of queries, m is the number of words in wordsContainer, and k is the average length of the strings.
Space Complexity: O(1), not accounting for the space used by character strings themselves, as we are only using scalar variables.
This approach involves using a Trie (prefix tree) for reversing the words, facilitating efficient suffix matching. By storing reversed words in the trie, we initiate with query word reversal and traverse the trie to determine the longest existing suffix efficiently, maintaining prefix search characteristics.
The Trie structure efficiently stores all reversed strings, with words stored backwards. During search, Trie nodes track the longest suffix index. This structure aids effective string traversal, swiftly furnishing the longest common suffix for each wordsQuery element.
Time Complexity: Trie insertion/search are O(k) on average, so full execution is O(n * k + m * k) where n/m are words/queries, each of k length. Efficiency is achieved owing to Trie operations.
Space Complexity: O(N * k), involving node storage at all levels for N words up to k letters.
The problem requires us to find the longest common suffix, so we can consider using a Trie.
We define the structure of the Trie node as follows:
children: An array of length 26, used to store child nodes.length: The length of the shortest string at the current node.idx: The index of the string at the current node.We traverse the string array wordsContainer, and insert each string in reverse order into the Trie. During the insertion process, we update the length and idx of each node.
Next, we traverse the string array wordsQuery. For each string, we search for the index of the longest common suffix string from the Trie. During the search process, if we encounter a null node, it means that there is no common suffix afterwards, and we can directly return the idx of the current node.
The time complexity is (L_1 times |\Sigma| + L_2), and the space complexity is O(L_1 times |\Sigma|). Here, L_1 and L_2 are the sum of the lengths of the strings in wordsContainer and wordsQuery respectively; and \Sigma is the size of the character set, in this problem \Sigma = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m * k), where n is the number of queries, m is the number of words in Space Complexity: O(1), not accounting for the space used by character strings themselves, as we are only using scalar variables. |
| Trie-based Optimized Approach | Time Complexity: Trie insertion/search are O(k) on average, so full execution is O(n * k + m * k) where n/m are words/queries, each of k length. Efficiency is achieved owing to Trie operations. Space Complexity: O(N * k), involving node storage at all levels for N words up to k letters. |
| Trie | — |
| 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 |
Longest Common Suffix Queries | Simple TRIE | Clean Code | Leetcode 3093 | codestorywithMIK • codestorywithMIK • 6,860 views views
Watch 9 more video solutions →Practice Longest Common Suffix Queries with our built-in code editor and test cases.
Practice on FleetCode