Longest Common Suffix Queries

hard trie string suffix

Problem

Given wordsContainer and wordsQuery, for each query find the container word sharing the longest common suffix with it. Ties go to the shortest container word, then to the one appearing earliest. Return the chosen indices.

Reversing every string turns “longest common suffix” into “longest common prefix”, so we build a trie of the reversed container words. Each trie node remembers the index of the best container word whose reversed form passes through it.

InputwordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]

Output[1,1,1]

All three queries land on index 1 (“bcd”) — it shares the common suffix and is the shortest container word (length 3).

wordsContainer (comma-separated)

wordsQuery (comma-separated)

def stringIndices(wordsContainer, wordsQuery):
    # better(i, j): is container i preferred over current best j?
    def better(i, j):
        if j == -1:
            return True
        li, lj = len(wordsContainer[i]), len(wordsContainer[j])
        return li < lj if li != lj else i < j

    # trie node = {ch: char->node, best: index of best word here}
    root = {"ch": {}, "best": -1}
    for i in range(len(wordsContainer)):       # empty-suffix winner
        if better(i, root["best"]):
            root["best"] = i

    for i, w in enumerate(wordsContainer):     # insert reversed words
        node = root
        for c in reversed(w):
            node = node["ch"].setdefault(c, {"ch": {}, "best": -1})
            if better(i, node["best"]):
                node["best"] = i

    ans = []
    for q in wordsQuery:                        # walk reversed query
        node, best = root, root["best"]
        for c in reversed(q):
            if c not in node["ch"]:
                break
            node = node["ch"][c]
            best = node["best"]
        ans.append(best)
    return ans

function stringIndices(wordsContainer, wordsQuery) {
  // better(i, j): is container i preferred over current best j?
  const better = (i, j) => {
    if (j === -1) return true;
    const li = wordsContainer[i].length, lj = wordsContainer[j].length;
    return li !== lj ? li < lj : i < j;
  };

  // trie node = { ch: Map char->node, best: index }
  const root = { ch: new Map(), best: -1 };
  for (let i = 0; i < wordsContainer.length; i++)  // empty-suffix winner
    if (better(i, root.best)) root.best = i;

  for (let i = 0; i < wordsContainer.length; i++) { // insert reversed
    let node = root;
    const w = wordsContainer[i];
    for (let k = w.length - 1; k >= 0; k--) {
      const c = w[k];
      if (!node.ch.has(c)) node.ch.set(c, { ch: new Map(), best: -1 });
      node = node.ch.get(c);
      if (better(i, node.best)) node.best = i;
    }
  }

  const ans = [];
  for (const q of wordsQuery) {                     // walk reversed query
    let node = root, best = root.best;
    for (let k = q.length - 1; k >= 0; k--) {
      if (!node.ch.has(q[k])) break;
      node = node.ch.get(q[k]);
      best = node.best;
    }
    ans.push(best);
  }
  return ans;
}

int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
    // node[0..25] children indices, node best stored in parallel arrays
    List<int[]> ch = new ArrayList<>();   // 26 child pointers per node
    List<Integer> best = new ArrayList<>();
    ch.add(new int[26]); Arrays.fill(ch.get(0), -1); best.add(-1);

    for (int i = 0; i < wordsContainer.length; i++)  // empty-suffix winner
        if (better(wordsContainer, i, best.get(0))) best.set(0, i);

    for (int i = 0; i < wordsContainer.length; i++) { // insert reversed
        int node = 0;
        String w = wordsContainer[i];
        for (int k = w.length() - 1; k >= 0; k--) {
            int c = w.charAt(k) - 'a';
            if (ch.get(node)[c] == -1) {
                ch.get(node)[c] = ch.size();
                int[] kids = new int[26]; Arrays.fill(kids, -1);
                ch.add(kids); best.add(-1);
            }
            node = ch.get(node)[c];
            if (better(wordsContainer, i, best.get(node))) best.set(node, i);
        }
    }

    int[] ans = new int[wordsQuery.length];
    for (int i = 0; i < wordsQuery.length; i++) {     // walk reversed query
        int node = 0, b = best.get(0);
        String q = wordsQuery[i];
        for (int k = q.length() - 1; k >= 0; k--) {
            int c = q.charAt(k) - 'a';
            if (ch.get(node)[c] == -1) break;
            node = ch.get(node)[c]; b = best.get(node);
        }
        ans[i] = b;
    }
    return ans;
}

// better(c, i, j): is container i preferred over current best j?
boolean better(String[] c, int i, int j) {
    if (j == -1) return true;
    int li = c[i].length(), lj = c[j].length();
    return li != lj ? li < lj : i < j;
}

vector<int> stringIndices(vector<string>& cont, vector<string>& query) {
    vector<array<int,26>> ch(1);            // 26 child pointers per node
    ch[0].fill(-1);
    vector<int> best(1, -1);
    auto better = [&](int i, int j) {       // i preferred over best j?
        if (j == -1) return true;
        int li = cont[i].size(), lj = cont[j].size();
        return li != lj ? li < lj : i < j;
    };

    for (int i = 0; i < (int)cont.size(); i++)   // empty-suffix winner
        if (better(i, best[0])) best[0] = i;

    for (int i = 0; i < (int)cont.size(); i++) {  // insert reversed
        int node = 0;
        for (int k = cont[i].size() - 1; k >= 0; k--) {
            int c = cont[i][k] - 'a';
            if (ch[node][c] == -1) {
                ch[node][c] = ch.size();
                ch.push_back({}); ch.back().fill(-1); best.push_back(-1);
            }
            node = ch[node][c];
            if (better(i, best[node])) best[node] = i;
        }
    }

    vector<int> ans;
    for (auto& q : query) {                       // walk reversed query
        int node = 0, b = best[0];
        for (int k = q.size() - 1; k >= 0; k--) {
            int c = q[k] - 'a';
            if (ch[node][c] == -1) break;
            node = ch[node][c]; b = best[node];
        }
        ans.push_back(b);
    }
    return ans;
}

Explanation

The key insight (Hint 1) is that the longest common suffix of two strings equals the longest common prefix of their reverses. So we reverse every word and reason about prefixes, which a trie handles naturally.

We build one trie from the reversed wordsContainer. As we insert word i, we visit every node along its reversed path. At each node we ask: is word i a better candidate than whatever is already stored there? “Better” means strictly shorter, and on a length tie, an earlier index. We keep only that single best index per node (Hint 2) — not a list — so the whole structure stays linear in the total input size.

The root represents the empty suffix that every word shares. Its stored best is the global winner, used when a query shares no suffix at all with any container word.

To answer a query, we reverse it and walk down the trie one character at a time. Each successful step means we matched one more character of common suffix, so we update best to the node we just reached. The moment a character has no child, we stop: that deepest reached node already holds the answer for the longest matched suffix.

Example: container ["abcd","bcd","xbcd"], query "cd". Reversed query is "dc". We walk d → c; every container word ends in “cd”, and the node after c stores index 1 (“bcd”, the shortest), so the answer is 1.