Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
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.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.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:
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.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.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 <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i] consists only of lowercase English letters.wordsQuery[i] consists only of lowercase English letters.wordsContainer[i].length is at most 5 * 105.wordsQuery[i].length is at most 5 * 105.Problem summary: 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].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Trie
["abcd","bcd","xbcd"] ["cd","bcd","xyz"]
["abcdefgh","poiuygh","ghghgh"] ["gh","acbfgh","acbfegh"]
longest-common-prefix)find-the-length-of-the-longest-common-prefix)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3093: Longest Common Suffix Queries
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;
}
}
// Accepted solution for LeetCode #3093: Longest Common Suffix Queries
const inf = 1 << 30
type Trie struct {
children [26]*Trie
length int
idx int
}
func newTrie() *Trie {
return &Trie{length: inf, idx: inf}
}
func (t *Trie) insert(w string, i int) {
node := t
if node.length > len(w) {
node.length = len(w)
node.idx = i
}
for k := len(w) - 1; k >= 0; k-- {
idx := int(w[k] - 'a')
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
if node.length > len(w) {
node.length = len(w)
node.idx = i
}
}
}
func (t *Trie) query(w string) int {
node := t
for k := len(w) - 1; k >= 0; k-- {
idx := int(w[k] - 'a')
if node.children[idx] == nil {
break
}
node = node.children[idx]
}
return node.idx
}
func stringIndices(wordsContainer []string, wordsQuery []string) (ans []int) {
trie := newTrie()
for i, w := range wordsContainer {
trie.insert(w, i)
}
for _, w := range wordsQuery {
ans = append(ans, trie.query(w))
}
return
}
# Accepted solution for LeetCode #3093: Longest Common Suffix Queries
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]
// Accepted solution for LeetCode #3093: Longest Common Suffix Queries
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3093: Longest Common Suffix Queries
// 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;
// }
// }
// Accepted solution for LeetCode #3093: Longest Common Suffix Queries
class Trie {
private children: Trie[] = new Array<Trie>(26);
private length: number = Infinity;
private idx: number = Infinity;
public insert(w: string, i: number): void {
let node: Trie = this;
if (node.length > w.length) {
node.length = w.length;
node.idx = i;
}
for (let k: number = w.length - 1; k >= 0; --k) {
let idx: number = w.charCodeAt(k) - 'a'.charCodeAt(0);
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 query(w: string): number {
let node: Trie = this;
for (let k: number = w.length - 1; k >= 0; --k) {
let idx: number = w.charCodeAt(k) - 'a'.charCodeAt(0);
if (node.children[idx] == null) {
break;
}
node = node.children[idx];
}
return node.idx;
}
}
function stringIndices(wordsContainer: string[], wordsQuery: string[]): number[] {
const trie: Trie = new Trie();
for (let i: number = 0; i < wordsContainer.length; ++i) {
trie.insert(wordsContainer[i], i);
}
const n: number = wordsQuery.length;
const ans: number[] = new Array<number>(n);
for (let i: number = 0; i < n; ++i) {
ans[i] = trie.query(wordsQuery[i]);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Store all N words in a hash set. Each insert/lookup hashes the entire word of length L, giving O(L) per operation. Prefix queries require checking every stored word against the prefix — O(N × L) per prefix search. Space is O(N × L) for storing all characters.
Each operation (insert, search, prefix) takes O(L) time where L is the word length — one node visited per character. Total space is bounded by the sum of all stored word lengths. Tries win over hash sets when you need prefix matching: O(L) prefix search vs. checking every stored word.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.