Skip to main content
Talentd

Longest Common Suffix Queries - Solution & Explanation

HardArrayStringTrie29 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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:

  • For 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.
  • For 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.
  • For 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:

  • For 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.
  • For 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.
  • For 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 <= 104
  • 1 <= wordsContainer[i].length <= 5 * 103
  • 1 <= wordsQuery[i].length <= 5 * 103
  • wordsContainer[i] consists only of lowercase English letters.
  • wordsQuery[i] consists only of lowercase English letters.
  • Sum of wordsContainer[i].length is at most 5 * 105.
  • Sum of wordsQuery[i].length is at most 5 * 105.

Approach Overview

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 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Trie-based Optimized Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Trie

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

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.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Suffix ComparisonO(Q * N * L)O(1)Small input sizes or quick prototype implementations
Trie with Reversed StringsO(N * L + Q * L)O(N * L)Large datasets with many queries requiring repeated suffix lookups

Video Solution

Longest Common Suffix Queries | Simple TRIE | Clean Code | Leetcode 3093 | codestorywithMIK • codestorywithMIK • 14,656 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Common Suffix Queries easy or hard?
Longest Common Suffix Queries is classified as a Hard problem because it requires recognizing that suffix comparisons can be converted into prefix operations using reversed strings and a Trie. Managing tie-breaking rules and storing optimal indices in the Trie nodes adds additional complexity.
How to solve Longest Common Suffix Queries in O(n)?
The problem can be solved near linear time by reversing strings and storing them in a Trie. Building the Trie costs O(N * L), and each query lookup costs O(L). By storing the best candidate index at every node during insertion, the correct answer can be returned immediately during traversal.
Longest Common Suffix Queries Python or Java solution
Both Python and Java implementations typically build a Trie using reversed container strings. Each node tracks the best candidate index based on suffix rules. Queries are reversed and traversed through the Trie in O(L) time to return the stored index.
What is the best approach for Longest Common Suffix Queries?
The Trie-based approach using reversed strings is the most efficient. Insert every container word reversed into a Trie and store the best candidate index at each node. Each query is also reversed and traversed through the Trie to find the longest matching suffix. This achieves O(N * L + Q * L) time complexity.
Is Longest Common Suffix Queries asked at Google/Amazon/Meta?
Trie-based string matching problems similar to Longest Common Suffix Queries frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of prefix trees, efficient string lookup, and optimization from brute force comparisons.
What data structure is used in Longest Common Suffix Queries?
The optimized solution uses a Trie (prefix tree). By reversing strings, suffix matching becomes prefix traversal in the Trie. Each node stores the best container index so queries can retrieve results quickly without scanning all words.
What is the time complexity of Longest Common Suffix Queries?
The brute force solution runs in O(Q * N * L) time where Q is the number of queries, N is the number of container words, and L is the maximum string length. The optimized Trie solution improves this to O(N * L + Q * L) because each word and query is processed only once through the Trie.

Ready to solve this problem?

Practice Longest Common Suffix Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Length of the Longest Common Prefix

Next

Longest Common Prefix