Longest Common Suffix Queries

Hard

#2747Time: O(M * N * L), where `M` is the number of queries, `N` is the number of container words, and `L` is the maximum length of a word. For each of `M` queries, we iterate through `N` container words, and comparing each pair takes up to `O(L)` time.Space: O(M) to store the answer array. Excluding the output, the space complexity is O(1).

Data structures

Array String Trie

Prompt

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 <= 10⁴
1 <= wordsContainer[i].length <= 5 * 10³
1 <= wordsQuery[i].length <= 5 * 10³
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 * 10⁵.
Sum of wordsQuery[i].length is at most 5 * 10⁵.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every string in wordsContainer for each query in wordsQuery. For each pair of query string and container string, we calculate the length of their common suffix. We maintain a record of the best container string found so far for the current query, based on the specified criteria: longest common suffix, then shortest length, then smallest index.

Algorithm

Find the index globalBestIndex of the shortest string in wordsContainer, breaking ties with the smaller index. This will be the default answer.
For each query in wordsQuery:
- Initialize bestIndex = globalBestIndex, maxSuffixLen = 0, and minLen to the length of the string at globalBestIndex.
- For each containerWord at index j in wordsContainer:
  - Calculate currentSuffixLen, the length of the common suffix between query and containerWord.
  - If currentSuffixLen > maxSuffixLen, update bestIndex = j, maxSuffixLen = currentSuffixLen, and minLen to containerWord's length.
  - Else if currentSuffixLen == maxSuffixLen and containerWord's length is less than minLen, update bestIndex = j and minLen.
- Store bestIndex as the result for the current query.
Return the array of results.

Walkthrough

The algorithm iterates through each query q from wordsQuery. For each q, it initializes variables to track the best match, starting with a default best candidate (the shortest word in the container, with the smallest index as a tie-breaker). It then enters a nested loop, iterating through every word w in wordsContainer. Inside the inner loop, a helper function calculates the length of the common suffix between q and w by comparing characters from the end of both strings backwards. This calculated suffix length is then compared against the best found so far. If the new suffix is longer, the current word w becomes the new best match. If the suffix length is the same, the length of w is checked; if it's shorter, it becomes the new best match. The smallest index tie-breaker is naturally handled by iterating through wordsContainer in order and only updating the best match when a strictly better candidate is found. This process is repeated for all queries.

1class Solution {2    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {3        int n = wordsContainer.length;4        int m = wordsQuery.length;5        int[] ans = new int[m];6 7        int globalShortestLen = Integer.MAX_VALUE;8        int globalBestIndex = 0;9        for (int i = 0; i < n; i++) {10            if (wordsContainer[i].length() < globalShortestLen) {11                globalShortestLen = wordsContainer[i].length();12                globalBestIndex = i;13            }14        }15 16        for (int i = 0; i < m; i++) {17            String query = wordsQuery[i];18            int bestIndex = globalBestIndex;19            int maxSuffixLen = 0;20            int minLen = globalShortestLen;21 22            for (int j = 0; j < n; j++) {23                String containerWord = wordsContainer[j];24                int currentSuffixLen = getCommonSuffixLength(query, containerWord);25 26                if (currentSuffixLen > maxSuffixLen) {27                    maxSuffixLen = currentSuffixLen;28                    minLen = containerWord.length();29                    bestIndex = j;30                } else if (currentSuffixLen == maxSuffixLen) {31                    if (containerWord.length() < minLen) {32                        minLen = containerWord.length();33                        bestIndex = j;34                    }35                }36            }37            ans[i] = bestIndex;38        }39        return ans;40    }41 42    private int getCommonSuffixLength(String s1, String s2) {43        int i = s1.length() - 1;44        int j = s2.length() - 1;45        int count = 0;46        while (i >= 0 && j >= 0 && s1.charAt(i) == s2.charAt(j)) {47            count++;48            i--;49            j--;50        }51        return count;52    }53}

Complexity

Time

O(M * N * L), where `M` is the number of queries, `N` is the number of container words, and `L` is the maximum length of a word. For each of `M` queries, we iterate through `N` container words, and comparing each pair takes up to `O(L)` time.

Space

O(M) to store the answer array. Excluding the output, the space complexity is O(1).

Trade-offs

Pros

Simple to understand and implement.
Low memory overhead as it does not require complex data structures.

Cons

Extremely inefficient for large inputs, likely causing a 'Time Limit Exceeded' error.
Performs a lot of redundant computations by repeatedly calculating suffix lengths for the same words.

This approach significantly improves performance by using a Trie (prefix tree). Since the problem is about common suffixes, we can reverse all strings in both wordsContainer and wordsQuery. The problem then becomes finding the longest common prefix. A Trie is an ideal data structure for this. We build a Trie from the reversed strings in wordsContainer and then search it for each reversed query string.

Algorithm

Define a TrieNode class with children (an array of 26 TrieNode pointers), minLength, and bestIndex attributes.
Create the root of the Trie. Find the index of the shortest word in wordsContainer (with tie-breaking) and use its length and index to initialize root.minLength and root.bestIndex.
For each word at index i in wordsContainer:
- Reverse the word.
- Traverse the Trie from the root, creating nodes as necessary for each character of the reversed word.
- For each node on the traversal path, if the current word's length is less than node.minLength, update node.minLength to the new minimum length and node.bestIndex to i.
For each query in wordsQuery:
- Reverse the query.
- Traverse the Trie from the root following the characters of the reversed query.
- Stop when a character is not found in the Trie (i.e., a child pointer is null).
- The bestIndex of the last node visited is the answer for this query.
Return the array of results.

Walkthrough

The core idea is to pre-process wordsContainer into a Trie. To handle the tie-breaking rules (shortest length, then smallest index), each node in the Trie will store information about the best word candidate among all words whose reversed form passes through it.

Trie Node Structure: Each node contains:

children: An array to child nodes for each character.
minLength: The length of the shortest word whose reversed form's prefix corresponds to the path to this node.
bestIndex: The original index in wordsContainer of the word corresponding to minLength.

Building and Querying: First, we build the Trie by inserting the reversed version of each word from wordsContainer. During insertion, as we traverse or create nodes, we update each node's minLength and bestIndex properties. A node's properties are updated if the current word being inserted is shorter than the word previously associated with that node. The smallest-index tie-breaker is handled implicitly by processing wordsContainer in its original order.

For each query, we reverse it and traverse the Trie. The deepest node we can reach corresponds to the longest common suffix. The bestIndex stored at this final node is the answer for the query. If a query has no common suffix with any container word, the traversal stops at the root, which holds the pre-calculated index of the overall shortest word.

1class TrieNode {2    TrieNode[] children;3    int minLength;4    int bestIndex;5 6    TrieNode() {7        children = new TrieNode[26];8        minLength = Integer.MAX_VALUE;9        bestIndex = -1;10    }11}12 13class Solution {14    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {15        TrieNode root = new TrieNode();16        17        int shortestLen = Integer.MAX_VALUE;18        int globalBestIndex = 0;19        for (int i = 0; i < wordsContainer.length; i++) {20            if (wordsContainer[i].length() < shortestLen) {21                shortestLen = wordsContainer[i].length();22                globalBestIndex = i;23            }24        }25        root.minLength = shortestLen;26        root.bestIndex = globalBestIndex;27 28        for (int i = 0; i < wordsContainer.length; i++) {29            String word = wordsContainer[i];30            int len = word.length();31            TrieNode curr = root;32            for (int j = len - 1; j >= 0; j--) {33                int charIndex = word.charAt(j) - 'a';34                if (curr.children[charIndex] == null) {35                    curr.children[charIndex] = new TrieNode();36                }37                curr = curr.children[charIndex];38                if (len < curr.minLength) {39                    curr.minLength = len;40                    curr.bestIndex = i;41                }42            }43        }44 45        int[] ans = new int[wordsQuery.length];46        for (int i = 0; i < wordsQuery.length; i++) {47            String query = wordsQuery[i];48            TrieNode curr = root;49            for (int j = query.length() - 1; j >= 0; j--) {50                int charIndex = query.charAt(j) - 'a';51                if (curr.children[charIndex] == null) {52                    break;53                }54                curr = curr.children[charIndex];55            }56            ans[i] = curr.bestIndex;57        }58 59        return ans;60    }61}

Complexity

Time

O(S_c + S_q), where `S_c` is the sum of lengths of all strings in `wordsContainer` and `S_q` is the sum of lengths of all strings in `wordsQuery`. Building the Trie takes `O(S_c)` and processing all queries takes `O(S_q)`.

Space

O(S_c), where `S_c` is the sum of lengths of all strings in `wordsContainer`. The number of nodes in the Trie is at most `S_c`, and each node stores a constant amount of information (an array of 26 pointers and two integers).

Trade-offs

Pros

Highly efficient time complexity, linear in the total length of all strings.
Effectively solves the problem by transforming the suffix search into a prefix search, which is what Tries excel at.

Cons

Higher space complexity due to the Trie data structure.
More complex to implement compared to the brute-force approach.

Solutions

Solution

1class Trie { private final int inf = 1 << 30 ; private Trie [] children = new Trie [ 26 ]; private int length = inf ; private int idx = inf ; public void insert ( String w , int i ) { Trie node = this ; if ( node . length > w . length ()) { node . length = w . length (); node . idx = i ; } for ( int k = w . length () - 1 ; k >= 0 ; -- k ) { int idx = w . charAt ( k ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; if ( node . length > w . length ()) { node . length = w . length (); node . idx = i ; } } } public int query ( String w ) { Trie node = this ; for ( int k = w . length () - 1 ; k >= 0 ; -- k ) { int idx = w . charAt ( k ) - 'a' ; if ( node . children [ idx ] == null ) { break ; } node = node . children [ idx ]; } return node . idx ; } } class Solution { public int [] stringIndices ( String [] wordsContainer , String [] wordsQuery ) { Trie trie = new Trie (); for ( int i = 0 ; i < wordsContainer . length ; ++ i ) { trie . insert ( wordsContainer [ i ], i ); } int n = wordsQuery . length ; int [] ans = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = trie . query ( wordsQuery [ i ]); } return ans ; } }

1class Trie { private: const int inf = 1 << 30 ; Trie * children [ 26 ]; int length = inf ; int idx = inf ; public: Trie () { for ( int i = 0 ; i < 26 ; ++ i ) { children [ i ] = nullptr ; } } void insert ( string w , int i ) { Trie * node = this ; if ( node -> length > w . length ()) { node -> length = w . length (); node -> idx = i ; } for ( int k = w . length () - 1 ; k >= 0 ; -- k ) { int idx = w [ k ] - 'a' ; if ( node -> children [ idx ] == nullptr ) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; if ( node -> length > w . length ()) { node -> length = w . length (); node -> idx = i ; } } } int query ( string w ) { Trie * node = this ; for ( int k = w . length () - 1 ; k >= 0 ; -- k ) { int idx = w [ k ] - 'a' ; if ( node -> children [ idx ] == nullptr ) { break ; } node = node -> children [ idx ]; } return node -> idx ; } }; class Solution { public: vector < int > stringIndices ( vector < string >& wordsContainer , vector < string >& wordsQuery ) { Trie * trie = new Trie (); for ( int i = 0 ; i < wordsContainer . size (); ++ i ) { trie -> insert ( wordsContainer [ i ], i ); } int n = wordsQuery . size (); vector < int > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = trie -> query ( wordsQuery [ i ]); } return ans ; } };

1class Trie : __slots__ = ( "children" , "length" , "idx" ) def __init__ ( self ): self . children = [ None ] * 26 self . length = inf self . idx = inf def insert ( self , w : str , i : int ): node = self if node . length > len ( w ): node . length = len ( w ) node . idx = i for c in w [:: - 1 ]: idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] if node . length > len ( w ): node . length = len ( w ) node . idx = i def query ( self , w : str ) -> int : node = self for c in w [:: - 1 ]: idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : break node = node . children [ idx ] return node . idx class Solution : def stringIndices ( self , wordsContainer : List [ str ], wordsQuery : List [ str ] ) -> List [ int ]: trie = Trie () for i , w in enumerate ( wordsContainer ): trie . insert ( w , i ) return [ trie . query ( w ) for w in wordsQuery ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem