# Longest Common Suffix Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-common-suffix-queries)
Canonical: https://scaleengineer.com/dsa/problems/longest-common-suffix-queries
**Data structures:** Array, String, Trie
---
## Problem
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`.

# Approaches
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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.

```java
class Solution {
    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        int n = wordsContainer.length;
        int m = wordsQuery.length;
        int[] ans = new int[m];

        int globalShortestLen = Integer.MAX_VALUE;
        int globalBestIndex = 0;
        for (int i = 0; i < n; i++) {
            if (wordsContainer[i].length() < globalShortestLen) {
                globalShortestLen = wordsContainer[i].length();
                globalBestIndex = i;
            }
        }

        for (int i = 0; i < m; i++) {
            String query = wordsQuery[i];
            int bestIndex = globalBestIndex;
            int maxSuffixLen = 0;
            int minLen = globalShortestLen;

            for (int j = 0; j < n; j++) {
                String containerWord = wordsContainer[j];
                int currentSuffixLen = getCommonSuffixLength(query, containerWord);

                if (currentSuffixLen > maxSuffixLen) {
                    maxSuffixLen = currentSuffixLen;
                    minLen = containerWord.length();
                    bestIndex = j;
                } else if (currentSuffixLen == maxSuffixLen) {
                    if (containerWord.length() < minLen) {
                        minLen = containerWord.length();
                        bestIndex = j;
                    }
                }
            }
            ans[i] = bestIndex;
        }
        return ans;
    }

    private int getCommonSuffixLength(String s1, String s2) {
        int i = s1.length() - 1;
        int j = s2.length() - 1;
        int count = 0;
        while (i >= 0 && j >= 0 && s1.charAt(i) == s2.charAt(j)) {
            count++;
            i--;
            j--;
        }
        return count;
    }
}
```
### 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.

## Optimized Search with a Trie on Reversed Strings
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.
**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).
**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.
### Explanation
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.

```java
class TrieNode {
    TrieNode[] children;
    int minLength;
    int bestIndex;

    TrieNode() {
        children = new TrieNode[26];
        minLength = Integer.MAX_VALUE;
        bestIndex = -1;
    }
}

class Solution {
    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        TrieNode root = new TrieNode();
        
        int shortestLen = Integer.MAX_VALUE;
        int globalBestIndex = 0;
        for (int i = 0; i < wordsContainer.length; i++) {
            if (wordsContainer[i].length() < shortestLen) {
                shortestLen = wordsContainer[i].length();
                globalBestIndex = i;
            }
        }
        root.minLength = shortestLen;
        root.bestIndex = globalBestIndex;

        for (int i = 0; i < wordsContainer.length; i++) {
            String word = wordsContainer[i];
            int len = word.length();
            TrieNode curr = root;
            for (int j = len - 1; j >= 0; j--) {
                int charIndex = word.charAt(j) - 'a';
                if (curr.children[charIndex] == null) {
                    curr.children[charIndex] = new TrieNode();
                }
                curr = curr.children[charIndex];
                if (len < curr.minLength) {
                    curr.minLength = len;
                    curr.bestIndex = i;
                }
            }
        }

        int[] ans = new int[wordsQuery.length];
        for (int i = 0; i < wordsQuery.length; i++) {
            String query = wordsQuery[i];
            TrieNode curr = root;
            for (int j = query.length() - 1; j >= 0; j--) {
                int charIndex = query.charAt(j) - 'a';
                if (curr.children[charIndex] == null) {
                    break;
                }
                curr = curr.children[charIndex];
            }
            ans[i] = curr.bestIndex;
        }

        return ans;
    }
}
```
### 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.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 ]
```