Longest Common Suffix Queries

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 integersans , whereans[i]is the index of the string inwordsContainer that has thelongest common suffix with wordsQuery[i].

Examples

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 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.
  * For `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.
  * For `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:

  * For `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.
  * 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 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 <= 10^4
• 1 <= wordsContainer[i].length <= 5 * 10^3
• 1 <= wordsQuery[i].length <= 5 * 10^3
• wordsContainer[i] consists only of lowercase English letters.
• wordsQuery[i] consists only of lowercase English letters.
• Sum of wordsContainer[i].length is at most 5 * 10^5.
• Sum of wordsQuery[i].length is at most 5 * 10^5.

Solution

Method 1 – Trie on Reversed Strings

Intuition

The problem requires finding the longest common suffix for each query, which naturally leads us to use a Trie data structure. However, since we need to match suffixes (not prefixes), we process all strings in reverse order when building and searching the Trie.

The key insight is to store at each Trie node the index of the best candidate word that can be reached through that path. The "best" candidate follows the tie-breaking rules: prefer longer common suffix, then shorter word length, then earlier index in the original array.

Approach

1. Initialize the Trie: Create a root node that initially points to the shortest word in wordsContainer (tie-broken by earliest index).

2. Build the Trie: For each word in wordsContainer, insert it into the Trie by traversing from the last character to the first (reverse order). At each node during insertion:

   • If the node doesn't exist, create it with the current word's index
   • If the node exists, update its stored index if the current word is shorter than the previously stored word

3. Process Queries: For each query word, traverse the Trie from the last character to the first:

   • Start with the root's stored index as the current best answer
   • At each step, if we can continue in the Trie, update the answer to the current node's stored index
   • If we can't continue further, return the last valid answer
   • This ensures we get the longest possible suffix match with proper tie-breaking

Note on C++ code: The TrieNode destructor recursively deletes all child nodes, ensuring proper memory cleanup. This is crucial for avoiding memory leaks, especially with large test cases where the Trie can grow significantly.

Code

C++

#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    int index;
    TrieNode* children[26];
    
    TrieNode(int idx = -1) : index(idx) {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
    
    ~TrieNode() {
        for (int i = 0; i < 26; i++) {
            if (children[i]) {
                delete children[i];
            }
        }
    }
};

class Solution {
private:
    void addWord(TrieNode* root, const vector<string>& wordsContainer, int wordIndex) {
        TrieNode* node = root;
        const string& word = wordsContainer[wordIndex];
        
        // Traverse from last character to first (reverse order for suffix matching)
        for (int i = word.length() - 1; i >= 0; i--) {
            int charIndex = word[i] - 'a';
            
            if (node->children[charIndex] == nullptr) {
                node->children[charIndex] = new TrieNode(wordIndex);
            }
            
            node = node->children[charIndex];
            
            // Update index if current word is shorter (better candidate)
            if (wordsContainer[node->index].length() > wordsContainer[wordIndex].length()) {
                node->index = wordIndex;
            }
        }
    }
    
    int searchQuery(TrieNode* root, const string& query) {
        TrieNode* node = root;
        int bestIndex = root->index;  // Start with root's stored index
        
        // Traverse from last character to first
        for (int i = query.length() - 1; i >= 0; i--) {
            int charIndex = query[i] - 'a';
            
            if (node->children[charIndex] == nullptr) {
                break;  // Can't continue further
            }
            
            node = node->children[charIndex];
            bestIndex = node->index;  // Update to current node's stored index
        }
        
        return bestIndex;
    }
    
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        // Initialize root with index of shortest word (tie-broken by earliest index)
        int shortestIndex = 0;
        for (int i = 1; i < wordsContainer.size(); i++) {
            if (wordsContainer[i].length() < wordsContainer[shortestIndex].length()) {
                shortestIndex = i;
            }
        }
        
        TrieNode* root = new TrieNode(shortestIndex);
        
        // Build trie with all words
        for (int i = 0; i < wordsContainer.size(); i++) {
            addWord(root, wordsContainer, i);
        }
        
        // Process all queries
        vector<int> result;
        result.reserve(wordsQuery.size());
        for (const string& query : wordsQuery) {
            result.push_back(searchQuery(root, query));
        }
        
        // Clean up memory - destructor will recursively delete all nodes
        delete root;
        
        return result;
    }
};

Go

type TrieNode struct {
    index    int
    children [26]*TrieNode
}

func NewTrieNode(idx int) *TrieNode {
    return &TrieNode{
        index:    idx,
        children: [26]*TrieNode{},
    }
}

func addWord(root *TrieNode, wordsContainer []string, wordIndex int) {
    node := root
    word := wordsContainer[wordIndex]
    
    // Traverse from last character to first (reverse order for suffix matching)
    for i := len(word) - 1; i >= 0; i-- {
        charIndex := word[i] - 'a'
        
        if node.children[charIndex] == nil {
            node.children[charIndex] = NewTrieNode(wordIndex)
        }
        
        node = node.children[charIndex]
        
        // Update index if current word is shorter (better candidate)
        if len(wordsContainer[node.index]) > len(wordsContainer[wordIndex]) {
            node.index = wordIndex
        }
    }
}

func searchQuery(root *TrieNode, query string) int {
    node := root
    bestIndex := root.index // Start with root's stored index
    
    // Traverse from last character to first
    for i := len(query) - 1; i >= 0; i-- {
        charIndex := query[i] - 'a'
        
        if node.children[charIndex] == nil {
            break // Can't continue further
        }
        
        node = node.children[charIndex]
        bestIndex = node.index // Update to current node's stored index
    }
    
    return bestIndex
}

func stringIndices(wordsContainer []string, wordsQuery []string) []int {
    // Initialize root with index of shortest word (tie-broken by earliest index)
    shortestIndex := 0
    for i := 1; i < len(wordsContainer); i++ {
        if len(wordsContainer[i]) < len(wordsContainer[shortestIndex]) {
            shortestIndex = i
        }
    }
    
    root := NewTrieNode(shortestIndex)
    
    // Build trie with all words
    for i := 0; i < len(wordsContainer); i++ {
        addWord(root, wordsContainer, i)
    }
    
    // Process all queries
    result := make([]int, len(wordsQuery))
    for i, query := range wordsQuery {
        result[i] = searchQuery(root, query)
    }
    
    return result
}

Java

class TrieNode {
    int index;
    TrieNode[] children;
    
    public TrieNode(int idx) {
        this.index = idx;
        this.children = new TrieNode[26];
    }
}

class Solution {
    private void addWord(TrieNode root, String[] wordsContainer, int wordIndex) {
        TrieNode node = root;
        String word = wordsContainer[wordIndex];
        
        // Traverse from last character to first (reverse order for suffix matching)
        for (int i = word.length() - 1; i >= 0; i--) {
            int charIndex = word.charAt(i) - 'a';
            
            if (node.children[charIndex] == null) {
                node.children[charIndex] = new TrieNode(wordIndex);
            }
            
            node = node.children[charIndex];
            
            // Update index if current word is shorter (better candidate)
            if (wordsContainer[node.index].length() > wordsContainer[wordIndex].length()) {
                node.index = wordIndex;
            }
        }
    }
    
    private int searchQuery(TrieNode root, String query) {
        TrieNode node = root;
        int bestIndex = root.index; // Start with root's stored index
        
        // Traverse from last character to first
        for (int i = query.length() - 1; i >= 0; i--) {
            int charIndex = query.charAt(i) - 'a';
            
            if (node.children[charIndex] == null) {
                break; // Can't continue further
            }
            
            node = node.children[charIndex];
            bestIndex = node.index; // Update to current node's stored index
        }
        
        return bestIndex;
    }
    
    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        // Initialize root with index of shortest word (tie-broken by earliest index)
        int shortestIndex = 0;
        for (int i = 1; i < wordsContainer.length; i++) {
            if (wordsContainer[i].length() < wordsContainer[shortestIndex].length()) {
                shortestIndex = i;
            }
        }
        
        TrieNode root = new TrieNode(shortestIndex);
        
        // Build trie with all words
        for (int i = 0; i < wordsContainer.length; i++) {
            addWord(root, wordsContainer, i);
        }
        
        // Process all queries
        int[] result = new int[wordsQuery.length];
        for (int i = 0; i < wordsQuery.length; i++) {
            result[i] = searchQuery(root, wordsQuery[i]);
        }
        
        return result;
    }
}

Kotlin

class TrieNode(var index: Int = -1) {
    val children = Array<TrieNode?>(26) { null }
}

class Solution {
    private fun addWord(root: TrieNode, wordsContainer: Array<String>, wordIndex: Int) {
        var node = root
        val word = wordsContainer[wordIndex]
        
        // Traverse from last character to first (reverse order for suffix matching)
        for (i in word.length - 1 downTo 0) {
            val charIndex = word[i] - 'a'
            
            if (node.children[charIndex] == null) {
                node.children[charIndex] = TrieNode(wordIndex)
            }
            
            node = node.children[charIndex]!!
            
            // Update index if current word is shorter (better candidate)
            if (wordsContainer[node.index].length > wordsContainer[wordIndex].length) {
                node.index = wordIndex
            }
        }
    }
    
    private fun searchQuery(root: TrieNode, query: String): Int {
        var node = root
        var bestIndex = root.index // Start with root's stored index
        
        // Traverse from last character to first
        for (i in query.length - 1 downTo 0) {
            val charIndex = query[i] - 'a'
            
            if (node.children[charIndex] == null) {
                break // Can't continue further
            }
            
            node = node.children[charIndex]!!
            bestIndex = node.index // Update to current node's stored index
        }
        
        return bestIndex
    }
    
    fun stringIndices(wordsContainer: Array<String>, wordsQuery: Array<String>): IntArray {
        // Initialize root with index of shortest word (tie-broken by earliest index)
        var shortestIndex = 0
        for (i in 1 until wordsContainer.size) {
            if (wordsContainer[i].length < wordsContainer[shortestIndex].length) {
                shortestIndex = i
            }
        }
        
        val root = TrieNode(shortestIndex)
        
        // Build trie with all words
        for (i in wordsContainer.indices) {
            addWord(root, wordsContainer, i)
        }
        
        // Process all queries
        val result = IntArray(wordsQuery.size)
        for (i in wordsQuery.indices) {
            result[i] = searchQuery(root, wordsQuery[i])
        }
        
        return result
    }
}

Python

class TrieNode:
    def __init__(self, index=-1):
        self.children = {}
        self.index = index

class Solution:
    def addWord(self, root: TrieNode, wordsContainer: list[str], wordIndex: int):
        node = root
        word = wordsContainer[wordIndex]
        
        # Traverse from last character to first (reverse order for suffix matching)
        for i in range(len(word) - 1, -1, -1):
            char = word[i]
            
            if char not in node.children:
                node.children[char] = TrieNode(wordIndex)
            
            node = node.children[char]
            
            # Update index if current word is shorter (better candidate)
            if len(wordsContainer[node.index]) > len(wordsContainer[wordIndex]):
                node.index = wordIndex
    
    def searchQuery(self, root: TrieNode, query: str) -> int:
        node = root
        bestIndex = root.index  # Start with root's stored index
        
        # Traverse from last character to first
        for i in range(len(query) - 1, -1, -1):
            char = query[i]
            
            if char not in node.children:
                break  # Can't continue further
            
            node = node.children[char]
            bestIndex = node.index  # Update to current node's stored index
        
        return bestIndex
    
    def stringIndices(self, wordsContainer: list[str], wordsQuery: list[str]) -> list[int]:
        # Initialize root with index of shortest word (tie-broken by earliest index)
        shortestIndex = 0
        for i in range(1, len(wordsContainer)):
            if len(wordsContainer[i]) < len(wordsContainer[shortestIndex]):
                shortestIndex = i
        
        root = TrieNode(shortestIndex)
        
        # Build trie with all words
        for i in range(len(wordsContainer)):
            self.addWord(root, wordsContainer, i)
        
        # Process all queries
        result = []
        for query in wordsQuery:
            result.append(self.searchQuery(root, query))
        
        return result

Rust

struct TrieNode {
    index: i32,
    children: [Option<Box<TrieNode>>; 26],
}

impl TrieNode {
    fn new(index: i32) -> Self {
        TrieNode {
            index,
            children: Default::default(),
        }
    }
}

impl Solution {
    fn add_word(root: &mut TrieNode, words_container: &[String], word_index: usize) {
        let mut node = root;
        let word = &words_container[word_index];
        
        // Traverse from last character to first (reverse order for suffix matching)
        for ch in word.chars().rev() {
            let char_index = (ch as u8 - b'a') as usize;
            
            if node.children[char_index].is_none() {
                node.children[char_index] = Some(Box::new(TrieNode::new(word_index as i32)));
            }
            
            node = node.children[char_index].as_mut().unwrap();
            
            // Update index if current word is shorter (better candidate)
            if words_container[node.index as usize].len() > words_container[word_index].len() {
                node.index = word_index as i32;
            }
        }
    }
    
    fn search_query(root: &TrieNode, query: &str) -> i32 {
        let mut node = root;
        let mut best_index = root.index; // Start with root's stored index
        
        // Traverse from last character to first
        for ch in query.chars().rev() {
            let char_index = (ch as u8 - b'a') as usize;
            
            if node.children[char_index].is_none() {
                break; // Can't continue further
            }
            
            node = node.children[char_index].as_ref().unwrap();
            best_index = node.index; // Update to current node's stored index
        }
        
        best_index
    }
    
    pub fn string_indices(words_container: Vec<String>, words_query: Vec<String>) -> Vec<i32> {
        // Initialize root with index of shortest word (tie-broken by earliest index)
        let mut shortest_index = 0;
        for i in 1..words_container.len() {
            if words_container[i].len() < words_container[shortest_index].len() {
                shortest_index = i;
            }
        }
        
        let mut root = TrieNode::new(shortest_index as i32);
        
        // Build trie with all words
        for i in 0..words_container.len() {
            Self::add_word(&mut root, &words_container, i);
        }
        
        // Process all queries
        let mut result = Vec::with_capacity(words_query.len());
        for query in &words_query {
            result.push(Self::search_query(&root, query));
        }
        
        result
    }
}

TypeScript

class TrieNode {
    index: number;
    children: (TrieNode | null)[];
    
    constructor(index: number = -1) {
        this.index = index;
        this.children = new Array(26).fill(null);
    }
}

function addWord(root: TrieNode, wordsContainer: string[], wordIndex: number): void {
    let node = root;
    const word = wordsContainer[wordIndex];
    
    // Traverse from last character to first (reverse order for suffix matching)
    for (let i = word.length - 1; i >= 0; i--) {
        const charIndex = word.charCodeAt(i) - 97; // 'a'.charCodeAt(0)
        
        if (node.children[charIndex] === null) {
            node.children[charIndex] = new TrieNode(wordIndex);
        }
        
        node = node.children[charIndex]!;
        
        // Update index if current word is shorter (better candidate)
        if (wordsContainer[node.index].length > wordsContainer[wordIndex].length) {
            node.index = wordIndex;
        }
    }
}

function searchQuery(root: TrieNode, query: string): number {
    let node = root;
    let bestIndex = root.index; // Start with root's stored index
    
    // Traverse from last character to first
    for (let i = query.length - 1; i >= 0; i--) {
        const charIndex = query.charCodeAt(i) - 97; // 'a'.charCodeAt(0)
        
        if (node.children[charIndex] === null) {
            break; // Can't continue further
        }
        
        node = node.children[charIndex]!;
        bestIndex = node.index; // Update to current node's stored index
    }
    
    return bestIndex;
}

function stringIndices(wordsContainer: string[], wordsQuery: string[]): number[] {
    // Initialize root with index of shortest word (tie-broken by earliest index)
    let shortestIndex = 0;
    for (let i = 1; i < wordsContainer.length; i++) {
        if (wordsContainer[i].length < wordsContainer[shortestIndex].length) {
            shortestIndex = i;
        }
    }
    
    const root = new TrieNode(shortestIndex);
    
    // Build trie with all words
    for (let i = 0; i < wordsContainer.length; i++) {
        addWord(root, wordsContainer, i);
    }
    
    // Process all queries
    const result: number[] = [];
    for (const query of wordsQuery) {
        result.push(searchQuery(root, query));
    }
    
    return result;
}

Complexity

• ⏰ Time complexity: O(N × L + Q × L), where N is the number of words in wordsContainer, Q is the number of queries in wordsQuery, and L is the maximum word length.

  • Building the Trie: O(N × L) - Each of the N words is processed character by character (up to L characters)
  • Processing queries: O(Q × L) - Each of the Q queries traverses the Trie up to L levels deep
  • Finding shortest word: O(N) - Linear scan through wordsContainer (absorbed into the dominant terms)

• 🧺 Space complexity: O(N × L), for storing the Trie structure. In the worst case, when no words share common suffixes, we create unique paths for each word, resulting in N × L nodes total.