3093. Longest Common Suffix Queries

Time: O(total container chars + total query chars)

Space: O(total container chars)

Intuition

Two words share a suffix when their reversed strings share a prefix. So we can turn suffix matching into prefix matching by inserting reversed container words into a trie. At each node, store the index of the shortest container word passing there (with earliest index tie behavior coming from insertion order updates), which gives the required answer for the best suffix match.

Algorithm

1Build a trie where each edge corresponds to a character of a word scanned from end to start.
2During insertion, move through reversed characters and update node metadata (shortest length and its index).
3Track minIndex globally as the shortest word in wordsContainer for full fallback.
4For each query, traverse the trie from query end to start.
5If traversal breaks, return the stored index of the deepest matched node; if none, fallback to minIndex.
6If traversal completes, return the current node index.

Example Walkthrough

Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]

1.Insert reversed container words: "dcba", "dcb", "dcbx" with node metadata tracking shortest candidate index.
2.Query "cd" -> reversed "dc": trie path exists, best index resolves to word "bcd" (shortest match).
3.Query "bcd" -> reversed "dcb": exact suffix path exists, again chooses shortest valid candidate.
4.Query "xyz" -> reversed "zyx": first edge missing, fallback to globally shortest container word index.

Output: [1, 1, 1]

Common Pitfalls

•This is suffix matching, so traversal must go from end to start; forward traversal solves a different problem.
•Fallback behavior matters: when no suffix matches, return the shortest container word index.
•Node metadata should represent the best candidate seen so far (shortest length, then earliest insertion semantics).

3093.cs

// Approach: Build a trie on reversed container words (suffix trie).
// Each trie node stores the index of the shortest word passing through it, so query traversal
// directly yields the best index for the longest matched suffix.
// Time: O(total container chars + total query chars) Space: O(total container chars)

public class Solution
{
    private TrieNode root = new TrieNode();

    public int[] StringIndices(string[] wordsContainer, string[] wordsQuery)
    {
        int[] ans = new int[wordsQuery.Length];
        int minIndex = 0;

        for (int i = 0; i < wordsContainer.Length; ++i)
        {
            Insert(wordsContainer[i], i);
            if (wordsContainer[i].Length < wordsContainer[minIndex].Length)
                minIndex = i;
        }

        for (int i = 0; i < wordsQuery.Length; ++i)
        {
            int index = Search(wordsQuery[i]);
            ans[i] = index == -1 ? minIndex : index;
        }

        return ans;
    }

    private void Insert(string word, int idx)
    {
        TrieNode node = root;
        for (int i = word.Length - 1; i >= 0; --i)
        {
            int index = word[i] - 'a';
            if (node.children[index] == null)
                node.children[index] = new TrieNode();
            node = node.children[index];
            if (node.length > word.Length)
            {
                node.length = word.Length;
                node.index = idx;
            }
        }
    }

    private int Search(string word)
    {
        TrieNode node = root;
        for (int i = word.Length - 1; i >= 0; --i)
        {
            int index = word[i] - 'a';
            if (node.children[index] == null)
                return node.index;
            node = node.children[index];
        }
        return node.index;
    }
}

class TrieNode
{
    public TrieNode[] children = new TrieNode[26];
    public bool isWord = false;
    public int length = int.MaxValue;
    public int index = -1;
}

Was this solution helpful?