3093. Longest Common Suffix Queries

Array
String
Trie

TIME

O(total container length + total query length)

SPACE

O(total container length)

Intuition

A suffix becomes a prefix if we read the word from right to left. So we can insert every container word into a trie in reversed order.

At each trie node, store the best container index among all words that pass through that node. "Best" means:

shortest word length
if lengths tie, smallest original index

Then a query walks the trie from its last character backward. The deepest node reached represents the longest common suffix, and that node already knows the correct tie-broken answer.

Approach

Create a reversed trie.
Insert every word from wordsContainer:
- update the root with this word, because the empty suffix is a valid fallback
- walk the word from right to left
- create missing trie nodes
- at every visited node, update the stored best index if this word is shorter, or equally short and earlier
For every query:
- start with the root's best index
- walk the query from right to left
- if the next character is missing, stop
- otherwise move to that node and use its stored best index as the current answer
Return all query answers.

Complexity

Let C be the total length of all strings in wordsContainer, and Q be the total length of all strings in wordsQuery.

Time: O(C + Q), every inserted or queried character is processed once
Space: O(C), one trie node per distinct reversed prefix

Edge Cases

No non-empty common suffix -> root returns the globally shortest earliest container word
Multiple words share the same suffix -> node-level tie-breaking chooses shortest then earliest
Duplicate container words -> earliest index wins
Query shorter than the matching container suffix -> traversal naturally stops at the query length

Code

from typing import List


class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        """
        3093. Longest Common Suffix Queries
        Time: O(total container length + total query length)
        Space: O(total container length)
        """
        children = [{}]
        best_index = [-1]
        best_length = [float("inf")]

        def update_best(node: int, word_index: int, word_length: int) -> None:
            if word_length < best_length[node] or (
                word_length == best_length[node] and word_index < best_index[node]
            ):
                best_length[node] = word_length
                best_index[node] = word_index

        for index, word in enumerate(wordsContainer):
            node = 0
            word_length = len(word)
            update_best(node, index, word_length)

            for char in reversed(word):
                if char not in children[node]:
                    children[node][char] = len(children)
                    children.append({})
                    best_index.append(-1)
                    best_length.append(float("inf"))
                node = children[node][char]
                update_best(node, index, word_length)

        answer = []
        for query in wordsQuery:
            node = 0
            result = best_index[node]

            for char in reversed(query):
                if char not in children[node]:
                    break
                node = children[node][char]
                result = best_index[node]

            answer.append(result)

        return answer

/**
 * 3093. Longest Common Suffix Queries
 * Time: O(total container length + total query length)
 * Space: O(total container length)
 */
class Solution {
    private int[][] children;
    private int[] bestIndex;
    private int[] bestLength;
    private int nodeCount;

    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        int maxNodes = 1;
        for (String word : wordsContainer) {
            maxNodes += word.length();
        }

        children = new int[maxNodes][26];
        bestIndex = new int[maxNodes];
        bestLength = new int[maxNodes];
        nodeCount = 1;

        for (int node = 0; node < maxNodes; node++) {
            bestIndex[node] = -1;
            bestLength[node] = Integer.MAX_VALUE;
        }

        for (int index = 0; index < wordsContainer.length; index++) {
            insert(wordsContainer[index], index);
        }

        int[] answer = new int[wordsQuery.length];
        for (int index = 0; index < wordsQuery.length; index++) {
            answer[index] = query(wordsQuery[index]);
        }

        return answer;
    }

    private void insert(String word, int wordIndex) {
        int node = 0;
        int wordLength = word.length();
        updateBest(node, wordIndex, wordLength);

        for (int index = wordLength - 1; index >= 0; index--) {
            int letter = word.charAt(index) - 'a';
            if (children[node][letter] == 0) {
                children[node][letter] = nodeCount++;
            }
            node = children[node][letter];
            updateBest(node, wordIndex, wordLength);
        }
    }

    private int query(String word) {
        int node = 0;
        int result = bestIndex[node];

        for (int index = word.length() - 1; index >= 0; index--) {
            int letter = word.charAt(index) - 'a';
            if (children[node][letter] == 0) {
                break;
            }
            node = children[node][letter];
            result = bestIndex[node];
        }

        return result;
    }

    private void updateBest(int node, int wordIndex, int wordLength) {
        if (
            wordLength < bestLength[node]
                || (wordLength == bestLength[node] && wordIndex < bestIndex[node])
        ) {
            bestLength[node] = wordLength;
            bestIndex[node] = wordIndex;
        }
    }
}