Longest Common Suffix Queries

Problem#

You are given wordsContainer and wordsQuery. For each query, return the index of the container word with the longest common suffix with the query. Ties go to the shortest word; further ties go to the smallest index.

Examples#

wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"] → [1,1,1].
wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"] → [2,0,2].

Constraints#

1 <= wordsContainer.length, wordsQuery.length <= 10^4, 1 <= word.length <= 5 * 10^3.

Hints#

Hint 1

Reverse every container word and insert into a trie — suffixes become prefixes.

Hint 2

At each trie node, remember the best container index that passes through it (shortest word, smallest index).

Approach#

Build a trie keyed on reversed container words. Each node remembers the best container index whose reversed string passes through that node (best by: shortest length, then smallest index). For each query, reverse it and walk the trie — return the best index at the deepest reachable node (or at the root if no characters match).

Solution#

class Solution {
    struct Node {
        Node* child[26]{};
        int bestIdx = -1;
    };
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        Node* root = new Node();
        auto better = [&](int a, int b) {
            if (a == -1) return b;
            if (b == -1) return a;
            int la = wordsContainer[a].size(), lb = wordsContainer[b].size();
            if (la != lb) return la < lb ? a : b;
            return a < b ? a : b;
        };
        for (int i = 0; i < (int)wordsContainer.size(); ++i) {
            Node* cur = root;
            cur->bestIdx = better(cur->bestIdx, i);
            const string& w = wordsContainer[i];
            for (int k = w.size() - 1; k >= 0; --k) {
                int idx = w[k] - 'a';
                if (!cur->child[idx]) cur->child[idx] = new Node();
                cur = cur->child[idx];
                cur->bestIdx = better(cur->bestIdx, i);
            }
        }
        vector<int> ans;
        ans.reserve(wordsQuery.size());
        for (auto& q : wordsQuery) {
            Node* cur = root;
            for (int k = q.size() - 1; k >= 0; --k) {
                int idx = q[k] - 'a';
                if (!cur->child[idx]) break;
                cur = cur->child[idx];
            }
            ans.push_back(cur->bestIdx);
        }
        return ans;
    }
};

type suffixNode struct {
    child   [26]*suffixNode
    bestIdx int
}

func stringIndices(wordsContainer []string, wordsQuery []string) []int {
    root := &suffixNode{bestIdx: -1}
    better := func(a, b int) int {
        if a == -1 {
            return b
        }
        if b == -1 {
            return a
        }
        la, lb := len(wordsContainer[a]), len(wordsContainer[b])
        if la != lb {
            if la < lb {
                return a
            }
            return b
        }
        if a < b {
            return a
        }
        return b
    }
    for i, w := range wordsContainer {
        cur := root
        cur.bestIdx = better(cur.bestIdx, i)
        for k := len(w) - 1; k >= 0; k-- {
            idx := w[k] - 'a'
            if cur.child[idx] == nil {
                cur.child[idx] = &suffixNode{bestIdx: -1}
            }
            cur = cur.child[idx]
            cur.bestIdx = better(cur.bestIdx, i)
        }
    }
    ans := make([]int, 0, len(wordsQuery))
    for _, q := range wordsQuery {
        cur := root
        for k := len(q) - 1; k >= 0; k-- {
            idx := q[k] - 'a'
            if cur.child[idx] == nil {
                break
            }
            cur = cur.child[idx]
        }
        ans = append(ans, cur.bestIdx)
    }
    return ans
}

from typing import List

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        class Node:
            __slots__ = ("child", "best_idx")

            def __init__(self) -> None:
                self.child: List[Node | None] = [None] * 26
                self.best_idx = -1

        root = Node()

        def better(a: int, b: int) -> int:
            if a == -1:
                return b
            if b == -1:
                return a
            la, lb = len(wordsContainer[a]), len(wordsContainer[b])
            if la != lb:
                return a if la < lb else b
            return a if a < b else b

        for i, w in enumerate(wordsContainer):
            cur = root
            cur.best_idx = better(cur.best_idx, i)
            for k in range(len(w) - 1, -1, -1):
                idx = ord(w[k]) - ord('a')
                if cur.child[idx] is None:
                    cur.child[idx] = Node()
                cur = cur.child[idx]
                cur.best_idx = better(cur.best_idx, i)

        ans = []
        for q in wordsQuery:
            cur = root
            for k in range(len(q) - 1, -1, -1):
                idx = ord(q[k]) - ord('a')
                if cur.child[idx] is None:
                    break
                cur = cur.child[idx]
            ans.append(cur.best_idx)
        return ans

function stringIndices(wordsContainer, wordsQuery) {
    const makeNode = () => ({ child: new Array(26).fill(null), bestIdx: -1 });
    const root = makeNode();
    const better = (a, b) => {
        if (a === -1) return b;
        if (b === -1) return a;
        const la = wordsContainer[a].length, lb = wordsContainer[b].length;
        if (la !== lb) return la < lb ? a : b;
        return a < b ? a : b;
    };
    for (let i = 0; i < wordsContainer.length; i++) {
        let cur = root;
        cur.bestIdx = better(cur.bestIdx, i);
        const w = wordsContainer[i];
        for (let k = w.length - 1; k >= 0; k--) {
            const idx = w.charCodeAt(k) - 97;
            if (!cur.child[idx]) cur.child[idx] = makeNode();
            cur = cur.child[idx];
            cur.bestIdx = better(cur.bestIdx, i);
        }
    }
    const ans = [];
    for (const q of wordsQuery) {
        let cur = root;
        for (let k = q.length - 1; k >= 0; k--) {
            const idx = q.charCodeAt(k) - 97;
            if (!cur.child[idx]) break;
            cur = cur.child[idx];
        }
        ans.push(cur.bestIdx);
    }
    return ans;
}

class TrieNode {
    TrieNode[] child = new TrieNode[26];
    int bestIdx = -1;
}

class Solution {
    private String[] container;

    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        this.container = wordsContainer;
        TrieNode root = new TrieNode();
        for (int i = 0; i < wordsContainer.length; i++) {
            TrieNode cur = root;
            cur.bestIdx = better(cur.bestIdx, i);
            String w = wordsContainer[i];
            for (int k = w.length() - 1; k >= 0; k--) {
                int idx = w.charAt(k) - 'a';
                if (cur.child[idx] == null) cur.child[idx] = new TrieNode();
                cur = cur.child[idx];
                cur.bestIdx = better(cur.bestIdx, i);
            }
        }
        int[] ans = new int[wordsQuery.length];
        for (int qi = 0; qi < wordsQuery.length; qi++) {
            String q = wordsQuery[qi];
            TrieNode cur = root;
            for (int k = q.length() - 1; k >= 0; k--) {
                int idx = q.charAt(k) - 'a';
                if (cur.child[idx] == null) break;
                cur = cur.child[idx];
            }
            ans[qi] = cur.bestIdx;
        }
        return ans;
    }

    private int better(int a, int b) {
        if (a == -1) return b;
        if (b == -1) return a;
        int la = container[a].length(), lb = container[b].length();
        if (la != lb) return la < lb ? a : b;
        return a < b ? a : b;
    }
}

interface SuffixNode {
    child: (SuffixNode | null)[];
    bestIdx: number;
}

function stringIndices(wordsContainer: string[], wordsQuery: string[]): number[] {
    const makeNode = (): SuffixNode => ({ child: new Array(26).fill(null), bestIdx: -1 });
    const root = makeNode();
    const better = (a: number, b: number): number => {
        if (a === -1) return b;
        if (b === -1) return a;
        const la = wordsContainer[a].length, lb = wordsContainer[b].length;
        if (la !== lb) return la < lb ? a : b;
        return a < b ? a : b;
    };
    for (let i = 0; i < wordsContainer.length; i++) {
        let cur = root;
        cur.bestIdx = better(cur.bestIdx, i);
        const w = wordsContainer[i];
        for (let k = w.length - 1; k >= 0; k--) {
            const idx = w.charCodeAt(k) - 97;
            if (!cur.child[idx]) cur.child[idx] = makeNode();
            cur = cur.child[idx] as SuffixNode;
            cur.bestIdx = better(cur.bestIdx, i);
        }
    }
    const ans: number[] = [];
    for (const q of wordsQuery) {
        let cur = root;
        for (let k = q.length - 1; k >= 0; k--) {
            const idx = q.charCodeAt(k) - 97;
            if (!cur.child[idx]) break;
            cur = cur.child[idx] as SuffixNode;
        }
        ans.push(cur.bestIdx);
    }
    return ans;
}

Editorial#

Reversing turns the suffix problem into a prefix problem the trie handles natively. The trick is per-node tie-breaking: while inserting each container word, update bestIdx on every node it passes through, comparing by (length asc, index asc). Queries then descend as far as possible and read the best index at the deepest node.

Complexity#

Time: O((W + Q) * L) where L is average word length.
Space: O(W * L).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#