Longest Common Suffix Queries solution and explanation
Google
9 more videos on this problem
Longest Common Suffix Queries | Simple TRIE | Clean Code | Leetcode 3093 | codestorywithMIKcodestorywithMIK · 48:34 · 14K views
3093. Longest Common Suffix Queries | Trie | Suffix Trie | Weekly Contest 390Aryan Mittal · 32:22 · 2K views
3093. Longest Common Suffix Queries | Leetcode Daily - PythonLeetcode Daily · 6:12 · 797 views
3093. Longest Common Suffix Queries | Weekly Leetcode 390codingMohan · 42:23 · 641 views
Longest Common Suffix Queries | LeetCode 3093 - Pythonimpoldev · 14:27 · 419 views
LeetCode Weekly Contest 390 Q4: Longest Common Suffix Queries (HARD)Alex does LeetCode · 6:35 · 378 views
3093. Longest Common Suffix Queries (Leetcode Hard)Programming Live with Larry · 16:53 · 323 views
Leetcode 3093. Longest Common Suffix QueriesExpertFunda · 25:35 · 246 views
3093 LeetCode | Longest Common Suffix Queries | Trie Explained Simply 🚀CodeSprint · 29:24 · 155 views
Longest Common Suffix Queries | LeetCode 3093 | Trie | Java Code | Developer CoderDeveloper Coder · 40:32 · 116 views
The problem
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:
- For
wordsQuery[0] = "cd", strings fromwordsContainerthat 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. - For
wordsQuery[1] = "bcd", strings fromwordsContainerthat 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. - For
wordsQuery[2] = "xyz", there is no string fromwordsContainerthat 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:
- For
wordsQuery[0] = "gh", strings fromwordsContainerthat 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. - For
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. - For
wordsQuery[2] = "acbfegh", strings fromwordsContainerthat 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.- Sum of
wordsContainer[i].lengthis at most5 * 105. - Sum of
wordsQuery[i].lengthis at most5 * 105.
Approach overview
Problem Overview: You receive two arrays of strings: wordsContainer and wordsQuery. For each query word, return the index of the container word sharing the longest common suffix. If multiple words share the same suffix length, choose the one with the shortest length, and if still tied, the smallest index.
The main challenge is efficiently comparing suffixes across many words. Direct comparisons work but become slow when both arrays are large. Reversing strings and using a Trie significantly reduces repeated comparisons.
Approach 1: Brute Force Suffix Comparison (O(Q * N * L) time, O(1) space)
For every query word, iterate through all words in wordsContainer. Compare characters from the end of both strings to compute the longest matching suffix. Track the best candidate using the rules: maximum suffix length, then minimum container word length, then smallest index. The comparison step costs up to O(L) per pair where L is the maximum string length. With Q queries and N container words, total complexity becomes O(Q * N * L). This approach is easy to implement but too slow for large inputs because it repeats suffix scans for every pair.
Approach 2: Trie on Reversed Strings (O(N * L + Q * L) time, O(N * L) space)
A more scalable approach uses a Trie. Since the problem focuses on suffixes, reverse every string in wordsContainer and insert it into the Trie character by character. While inserting, store at each node the index of the best candidate word according to the tie-breaking rules (shortest length, then smallest index). This ensures that every prefix of the reversed string already knows the optimal answer.
When processing a query, reverse it and traverse the Trie character by character. Each step corresponds to extending the suffix match. If traversal stops because a character path is missing, return the best index stored at the deepest node reached. Since traversal only follows the query length, each query costs O(L). Trie construction costs O(N * L). This reduces repeated comparisons and efficiently handles large datasets.
This approach relies on concepts from string processing and prefix trees commonly used for fast lookup problems involving shared prefixes or suffixes.
Recommended for interviews: Interviewers expect the Trie-based optimization. The brute force approach demonstrates understanding of suffix comparison and tie-breaking rules, but the optimized Trie solution shows the ability to transform a suffix problem into a prefix structure by reversing strings and caching the best candidate at each node.
Approach 1: Brute Force Approach
This approach involves reversing both the wordsContainer and wordsQuery strings. By doing so, the problem of finding the longest common suffix is converted into finding the longest common prefix, which can be done directly by comparing characters sequentially. For each query word, check all words in the container and determine which word provides the longest common prefix when reversed. Handle ties by choosing the shortest word or the earliest occurring one.
def longest_common_suffix_length(a, b):
i, j = len(a) - 1, len(b) - 1
length = 0
while i >= 0 and j >= 0 and a[i] == b[j]:
length += 1
i -= 1
j -= 1
return length
def find_best_match(words_container, query):
max_len = 0
min_length = float('inf')
best_index = -1
for i, word in enumerate(words_container):
current_len = longest_common_suffix_length(word, query)
if current_len > max_len or (current_len == max_len and len(word) < min_length):
max_len = current_len
min_length = len(word)
best_index = i
return best_index
def longest_common_suffix_queries(words_container, words_query):
return [find_best_match(words_container, query) for query in words_query]
words_container = ["abcd", "bcd", "xbcd"]
words_query = ["cd", "bcd", "xyz"]
result = longest_common_suffix_queries(words_container, words_query)
print(result)import java.util.Arrays;
import java.util.List;
public class LongestCommonSuffix {
private static int longestCommonSuffixLength(String a, String b) {
int length = 0;
int i = a.length() - 1, j = b.length() - 1;
while (i >= 0 && j >= 0 && a.charAt(i) == b.charAt(j)) {
length++;
i--;
j--;
}
return length;
}
private static int findBestMatch(List<String> wordsContainer, String query) {
int maxLen = 0;
int minLength = Integer.MAX_VALUE;
int bestIndex = -1;
for (int i = 0; i < wordsContainer.size(); i++) {
String word = wordsContainer.get(i);
int currentLen = longestCommonSuffixLength(word, query);
if (currentLen > maxLen || (currentLen == maxLen && word.length() < minLength)) {
maxLen = currentLen;
minLength = word.length();
bestIndex = i;
}
}
return bestIndex;
}
public static int[] longestCommonSuffixQueries(List<String> wordsContainer, List<String> wordsQuery) {
int[] result = new int[wordsQuery.size()];
for (int i = 0; i < wordsQuery.size(); i++) {
result[i] = findBestMatch(wordsContainer, wordsQuery.get(i));
}
return result;
}
public static void main(String[] args) {
List<String> wordsContainer = Arrays.asList("abcd", "bcd", "xbcd");
List<String> wordsQuery = Arrays.asList("cd", "bcd", "xyz");
int[] result = longestCommonSuffixQueries(wordsContainer, wordsQuery);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestCommonSuffixLength(const string &a, const string &b) {
int i = a.size() - 1;
int j = b.size() - 1;
int length = 0;
while (i >= 0 && j >= 0 && a[i] == b[j]) {
length++;
i--;
j--;
}
return length;
}
int findBestMatch(const vector<string> &wordsContainer, const string &query) {
int maxLen = 0;
int minLength = INT_MAX;
int bestIndex = -1;
for (size_t i = 0; i < wordsContainer.size(); ++i) {
int currentLen = longestCommonSuffixLength(wordsContainer[i], query);
if (currentLen > maxLen || (currentLen == maxLen && wordsContainer[i].size() < minLength)) {
maxLen = currentLen;
minLength = wordsContainer[i].size();
bestIndex = i;
}
}
return bestIndex;
}
vector<int> longestCommonSuffixQueries(const vector<string> &wordsContainer, const vector<string> &queries) {
vector<int> result;
result.reserve(queries.size());
for (const auto &query : queries) {
result.push_back(findBestMatch(wordsContainer, query));
}
return result;
}
int main() {
vector<string> wordsContainer = {"abcd", "bcd", "xbcd"};
vector<string> wordsQuery = {"cd", "bcd", "xyz"};
vector<int> result = longestCommonSuffixQueries(wordsContainer, wordsQuery);
for (int index : result) {
cout << index << " ";
}
return 0;
}function longestCommonSuffixLength(a, b) {
let length = 0;
let i = a.length - 1, j = b.length - 1;
while (i >= 0 && j >= 0 && a[i] === b[j]) {
length++;
i--;
j--;
}
return length;
}
function findBestMatch(wordsContainer, query) {
let maxLen = 0;
let minLength = Infinity;
let bestIndex = -1;
for (let i = 0; i < wordsContainer.length; i++) {
let currentLen = longestCommonSuffixLength(wordsContainer[i], query);
if (currentLen > maxLen || (currentLen === maxLen && wordsContainer[i].length < minLength)) {
maxLen = currentLen;
minLength = wordsContainer[i].length;
bestIndex = i;
}
}
return bestIndex;
}
function longestCommonSuffixQueries(wordsContainer, wordsQuery) {
return wordsQuery.map(query => findBestMatch(wordsContainer, query));
}
const wordsContainer = ["abcd", "bcd", "xbcd"];
const wordsQuery = ["cd", "bcd", "xyz"];
const result = longestCommonSuffixQueries(wordsContainer, wordsQuery);
console.log(result);#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int longestCommonSuffixLength(char *a, char *b) {
int len_a = strlen(a);
int len_b = strlen(b);
int i = len_a - 1, j = len_b - 1;
int length = 0;
while (i >= 0 && j >= 0 && a[i] == b[j]) {
length++;
i--;
j--;
}
return length;
}
int findBestMatch(char **wordsContainer, int containerSize, char *query) {
int maxLen = 0;
int minLength = 5001; // given constraint
int bestIndex = -1;
for (int i = 0; i < containerSize; i++) {
int currentLen = longestCommonSuffixLength(wordsContainer[i], query);
if (currentLen > maxLen || (currentLen == maxLen && strlen(wordsContainer[i]) < minLength)) {
maxLen = currentLen;
minLength = strlen(wordsContainer[i]);
bestIndex = i;
}
}
return bestIndex;
}
int* longestCommonSuffixQueries(char **wordsContainer, int containerSize, char **queries, int queriesSize, int *returnSize) {
*returnSize = queriesSize;
int *result = (int *)malloc(sizeof(int) * queriesSize);
for (int i = 0; i < queriesSize; i++) {
result[i] = findBestMatch(wordsContainer, containerSize, queries[i]);
}
return result;
}
int main() {
char *wordsContainer[] = {"abcd", "bcd", "xbcd"};
char *wordsQuery[] = {"cd", "bcd", "xyz"};
int returnSize;
int *result = longestCommonSuffixQueries(wordsContainer, 3, wordsQuery, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
class Program
{
static int LongestCommonSuffixLength(string a, string b)
{
int length = 0;
int i = a.Length - 1, j = b.Length - 1;
while (i >= 0 && j >= 0 && a[i] == b[j])
{
length++;
i--;
j--;
}
return length;
}
static int FindBestMatch(List<string> wordsContainer, string query)
{
int maxLen = 0;
int minLength = int.MaxValue;
int bestIndex = -1;
for (int i = 0; i < wordsContainer.Count; i++)
{
int currentLen = LongestCommonSuffixLength(wordsContainer[i], query);
if (currentLen > maxLen || (currentLen == maxLen && wordsContainer[i].Length < minLength))
{
maxLen = currentLen;
minLength = wordsContainer[i].Length;
bestIndex = i;
}
}
return bestIndex;
}
static int[] LongestCommonSuffixQueries(List<string> wordsContainer, List<string> wordsQuery)
{
int[] result = new int[wordsQuery.Count];
for (int i = 0; i < wordsQuery.Count; i++)
{
result[i] = FindBestMatch(wordsContainer, wordsQuery[i]);
}
return result;
}
static void Main()
{
List<string> wordsContainer = new List<string> { "abcd", "bcd", "xbcd" };
List<string> wordsQuery = new List<string> { "cd", "bcd", "xyz" };
int[] result = LongestCommonSuffixQueries(wordsContainer, wordsQuery);
foreach (int index in result)
{
Console.Write(index + " ");
}
}
}This solution checks the longest suffix by aligning the end indices of both query and container words. It calculates the length of the suffix that both share, iterating backwards. Each query goes through the wordsContainer seeking the optimal suffix.
Time Complexity: O(n * m * k), where n is the number of queries, m is the number of container words, and k is their average length.
Space Complexity: O(1) aside from the required storage of words, as no extra lists or arrays are created.
Approach 2: Trie-based Optimized Approach
This approach involves using a Trie (prefix tree) for reversing the words, facilitating efficient suffix matching. By storing reversed words in the trie, we initiate with query word reversal and traverse the trie to determine the longest existing suffix efficiently, maintaining prefix search characteristics.
class TrieNode:
def __init__(self):
self.children = {}
self.index = -1
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word, idx):
node = self.root
for ch in reversed(word):
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.index = idx
def search(self, word):
node = self.root
longest_index = -1
length = 0
for ch in reversed(word):
if ch not in node.children:
break
node = node.children[ch]
length += 1
if node.index != -1:
longest_index = node.index
return longest_index
def longest_common_suffix_queries(words_container, words_query):
trie = Trie()
for idx, word in enumerate(words_container):
trie.insert(word, idx)
return [trie.search(query) for query in words_query]
words_container = ["abcd", "bcd", "xbcd"]
words_query = ["cd", "bcd", "xyz"]
result = longest_common_suffix_queries(words_container, words_query)
print(result)import java.util.List;
class TrieNode {
TrieNode[] children;
int index;
TrieNode() {
children = new TrieNode[26];
index = -1;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word, int idx) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; i--) {
int ch = word.charAt(i) - 'a';
if (node.children[ch] == null)
node.children[ch] = new TrieNode();
node = node.children[ch];
}
node.index = idx;
}
public int search(String word) {
TrieNode node = root;
int longestIndex = -1, length = 0;
for (int i = word.length() - 1; i >= 0; i--) {
int ch = word.charAt(i) - 'a';
if (node.children[ch] == null)
break;
node = node.children[ch];
length++;
if (node.index != -1)
longestIndex = node.index;
}
return longestIndex;
}
}
public class SuffixQueries {
public static int[] longestCommonSuffixQueries(List<String> wordsContainer, List<String> wordsQuery) {
Trie trie = new Trie();
for (int i = 0; i < wordsContainer.size(); i++) {
trie.insert(wordsContainer.get(i), i);
}
int[] result = new int[wordsQuery.size()];
for (int i = 0; i < wordsQuery.size(); i++) {
result[i] = trie.search(wordsQuery.get(i));
}
return result;
}
public static void main(String[] args) {
List<String> wordsContainer = List.of("abcd", "bcd", "xbcd");
List<String> wordsQuery = List.of("cd", "bcd", "xyz");
int[] results = longestCommonSuffixQueries(wordsContainer, wordsQuery);
for (int res : results) {
System.out.print(res + " ");
}
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
class TrieNode {
public:
vector<TrieNode *> children;
int index;
TrieNode() : children(26, nullptr), index(-1) {}
};
class Trie {
private:
TrieNode *root;
public:
Trie() : root(new TrieNode()) {}
void insert(const string &word, int idx) {
TrieNode *node = root;
for (int i = word.size() - 1; i >= 0; --i) {
int charIndex = word[i] - 'a';
if (!node->children[charIndex])
node->children[charIndex] = new TrieNode();
node = node->children[charIndex];
}
node->index = idx;
}
pair<int, int> search(const string &word) {
TrieNode *node = root;
int length = 0, longestIndex = -1;
for (int i = word.size() - 1; i >= 0; --i) {
int charIndex = word[i] - 'a';
if (!node->children[charIndex])
break;
node = node->children[charIndex];
length++;
if (node->index != -1)
longestIndex = node->index;
}
return {longestIndex, length};
}
};
vector<int> longestCommonSuffixQueries(const vector<string> &wordsContainer, const vector<string> &queries) {
Trie trie;
for (int i = 0; i < wordsContainer.size(); ++i) {
trie.insert(wordsContainer[i], i);
}
vector<int> result;
result.reserve(queries.size());
for (const auto &query : queries) {
auto [index, length] = trie.search(query);
result.push_back(index);
}
return result;
}
int main() {
vector<string> wordsContainer = {"abcd", "bcd", "xbcd"};
vector<string> wordsQuery = {"cd", "bcd", "xyz"};
vector<int> result = longestCommonSuffixQueries(wordsContainer, wordsQuery);
for (const auto &index : result) {
cout << index << " ";
}
return 0;
}class TrieNode {
constructor() {
this.children = {};
this.index = -1;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word, idx) {
let node = this.root;
for (let i = word.length - 1; i >= 0; i--) {
const char = word[i];
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.index = idx;
}
search(word) {
let node = this.root;
let longestIndex = -1;
for (let i = word.length - 1; i >= 0; i--) {
const char = word[i];
if (!node.children[char]) {
break;
}
node = node.children[char];
if (node.index !== -1) lo பரக்கு.
}
return longestIndex;
}
}
function longestCommonSuffixQueries(wordsContainer, wordsQuery) {
const trie = new Trie();
wordsContainer.forEach((word, idx) => trie.insert(word, idx));
return wordsQuery.map(query => trie.search(query));
}
const wordsContainer = ["abcd", "bcd", "xbcd"];
const wordsQuery = ["cd", "bcd", "xyz"];
console.log(longestCommonSuffixQueries(wordsContainer, wordsQuery));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
// Trie node
typedef struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
int index; // to store the index of the word in wordsContainer
} TrieNode;
// Returns new trie node (initialized to NULL)
TrieNode *getNode(void) {
TrieNode *pNode = (TrieNode *)malloc(sizeof(TrieNode));
pNode->index = -1;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
// Insert word into the trie
void insert(TrieNode *root, const char *word, int index) {
TrieNode *pCrawl = root;
int length = strlen(word);
for (int level = length - 1; level >= 0; level--) {
int index_char = CHAR_TO_INDEX(word[level]);
if (!pCrawl->children[index_char])
pCrawl->children[index_char] = getNode();
pCrawl = pCrawl->children[index_char];
}
pCrawl->index = index; // store index at leaf node
}
// Search for the longest suffix of the word in trie
typedef struct SuffixSearchResult {
int index;
int length;
} SuffixSearchResult;
SuffixSearchResult searchLongestSuffix(TrieNode *root, const char *word) {
TrieNode *pCrawl = root;
int length = 0;
int longestIndex = -1;
int word_len = strlen(word);
for (int level = word_len - 1; level >= 0; level--) {
int index_char = CHAR_TO_INDEX(word[level]);
if (!pCrawl->children[index_char])
break;
pCrawl = pCrawl->children[index_char];
length++;
if (pCrawl->index != -1)
longestIndex = pCrawl->index;
}
SuffixSearchResult result = {longestIndex, length};
return result;
}
int *longestCommonSuffixQueries(char **wordsContainer, int containerSize, char **queries, int queriesSize, int *returnSize) {
*returnSize = queriesSize;
int *result = (int *)malloc(sizeof(int) * queriesSize);
TrieNode *root = getNode();
// Insert all the words in wordsContainer after reversing them
for (int i = 0; i < containerSize; i++) {
insert(root, wordsContainer[i], i);
}
SuffixSearchResult suffixSearchResult;
for (int i = 0; i < queriesSize; i++) {
suffixSearchResult = searchLongestSuffix(root, queries[i]);
result[i] = suffixSearchResult.index;
}
// Freeing memory (In actual practice, this would be more thorough.)
free(root);
return result;
}
int main() {
char *wordsContainer[] = {"abcd", "bcd", "xbcd"};
char *wordsQuery[] = {"cd", "bcd", "xyz"};
int returnSize;
int *result = longestCommonSuffixQueries(wordsContainer, 3, wordsQuery, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
class TrieNode
{
public TrieNode[] Children;
public int Index;
public TrieNode()
{
Children = new TrieNode[26];
Index = -1;
}
}
class Trie
{
private TrieNode root;
public Trie()
{
root = new TrieNode();
}
public void Insert(string word, int index)
{
TrieNode node = root;
for (int i = word.Length - 1; i >= 0; i--)
{
int charIndex = word[i] - 'a';
if (node.Children[charIndex] == null)
node.Children[charIndex] = new TrieNode();
node = node.Children[charIndex];
}
node.Index = index;
}
public int Search(string word)
{
TrieNode node = root;
int longestIndex = -1, length = 0;
for (int i = word.Length - 1; i >= 0; i--)
{
int charIndex = word[i] - 'a';
if (node.Children[charIndex] == null)
break;
node = node.Children[charIndex];
length++;
if (node.Index != -1)
longestIndex = node.Index;
}
return longestIndex;
}
}
class SuffixQueries
{
public static int[] LongestCommonSuffixQueries(List<string> wordsContainer, List<string> wordsQuery)
{
Trie trie = new Trie();
for (int i = 0; i < wordsContainer.Count; i++)
{
trie.Insert(wordsContainer[i], i);
}
int[] result = new int[wordsQuery.Count];
for (int i = 0; i < wordsQuery.Count; i++)
{
result[i] = trie.Search(wordsQuery[i]);
}
return result;
}
public static void Main()
{
List<string> wordsContainer = new List<string> { "abcd", "bcd", "xbcd" };
List<string> wordsQuery = new List<string> { "cd", "bcd", "xyz" };
var results = LongestCommonSuffixQueries(wordsContainer, wordsQuery);
Console.WriteLine(string.Join(" ", results));
}
}This algorithm utilizes Trie data structures, reversing words into trie trees to facilitate swift and systematic word suffix discoveries. Trie nodes are assigned indices representing indices of first discoveries or longest path per node level.
Time Complexity: O(N * k + M * k) due to Trie insertions and searches managing nodes distributed across possible letters in string lengths.
Space Complexity: Nodes accommodate space proportional to words (N * k) stored in Trie branches per character.
Approach 3: Trie
The problem requires us to find the longest common suffix, so we can consider using a Trie.
We define the structure of the Trie node as follows:
children: An array of length 26, used to store child nodes.length: The length of the shortest string at the current node.idx: The index of the string at the current node.
We traverse the string array wordsContainer, and insert each string in reverse order into the Trie. During the insertion process, we update the length and idx of each node.
Next, we traverse the string array wordsQuery. For each string, we search for the index of the longest common suffix string from the Trie. During the search process, if we encounter a null node, it means that there is no common suffix afterwards, and we can directly return the idx of the current node.
The time complexity is (L_1 times |\Sigma| + L_2), and the space complexity is O(L_1 times |\Sigma|). Here, L_1 and L_2 are the sum of the lengths of the strings in wordsContainer and wordsQuery respectively; and \Sigma is the size of the character set, in this problem \Sigma = 26.
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m * k), where n is the number of queries, m is the number of container words, and k is their average length. Space Complexity: O(1) aside from the required storage of words, as no extra lists or arrays are created. |
| Trie-based Optimized Approach | Time Complexity: O(N * k + M * k) due to Trie insertions and searches managing nodes distributed across possible letters in string lengths. Space Complexity: Nodes accommodate space proportional to words (N * k) stored in Trie branches per character. |
| Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Suffix Comparison | O(Q * N * L) | O(1) | Small input sizes or quick prototype implementations |
| Trie with Reversed Strings | O(N * L + Q * L) | O(N * L) | Large datasets with many queries requiring repeated suffix lookups |
Frequently asked questions
Is Longest Common Suffix Queries easy or hard?
Longest Common Suffix Queries is classified as a Hard problem because it requires recognizing that suffix comparisons can be converted into prefix operations using reversed strings and a Trie. Managing tie-breaking rules and storing optimal indices in the Trie nodes adds additional complexity.
How to solve Longest Common Suffix Queries in O(n)?
The problem can be solved near linear time by reversing strings and storing them in a Trie. Building the Trie costs O(N * L), and each query lookup costs O(L). By storing the best candidate index at every node during insertion, the correct answer can be returned immediately during traversal.
Longest Common Suffix Queries Python or Java solution
Both Python and Java implementations typically build a Trie using reversed container strings. Each node tracks the best candidate index based on suffix rules. Queries are reversed and traversed through the Trie in O(L) time to return the stored index.
What is the best approach for Longest Common Suffix Queries?
The Trie-based approach using reversed strings is the most efficient. Insert every container word reversed into a Trie and store the best candidate index at each node. Each query is also reversed and traversed through the Trie to find the longest matching suffix. This achieves O(N * L + Q * L) time complexity.
Is Longest Common Suffix Queries asked at Google/Amazon/Meta?
Trie-based string matching problems similar to Longest Common Suffix Queries frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of prefix trees, efficient string lookup, and optimization from brute force comparisons.
What data structure is used in Longest Common Suffix Queries?
The optimized solution uses a Trie (prefix tree). By reversing strings, suffix matching becomes prefix traversal in the Trie. Each node stores the best container index so queries can retrieve results quickly without scanning all words.
What is the time complexity of Longest Common Suffix Queries?
The brute force solution runs in O(Q * N * L) time where Q is the number of queries, N is the number of container words, and L is the maximum string length. The optimized Trie solution improves this to O(N * L + Q * L) because each word and query is processed only once through the Trie.