We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Suffix Queries

Number: 3376

Difficulty: Hard

Paid? No

Companies: Bloomberg, Google

Problem Description

Given two arrays of strings, wordsContainer and wordsQuery, for each query string in wordsQuery find the index of a string in wordsContainer that shares the longest common suffix with it. If multiple words share the same longest common suffix then choose the one with the smallest length, and if there is still a tie, choose the one that appears earliest in wordsContainer.

Key Insights

  • Reverse the strings so that finding a common suffix becomes equivalent to finding a common prefix.
  • Build a Trie (prefix tree) using the reversed words from wordsContainer.
  • At each Trie node, store the best candidate word (based on smallest overall length, then smallest index) among all words that pass through that node.
  • For each query, traverse the Trie according to the reversed query string to determine how many characters match and use the stored candidate from the last matched node.
  • If no characters match (i.e. common suffix is empty), use the candidate from the root, which represents the empty suffix shared by all.

Space and Time Complexity

Time Complexity: O(S + Q) where S is the sum of lengths of all strings in wordsContainer and Q is the sum of lengths of all strings in wordsQuery. Space Complexity: O(S) for the Trie data structure.

Solution

We solve the problem by building a Trie that is constructed from the reversed words in wordsContainer. Each node in the Trie holds a candidate that is the best index yielding a word with the smallest length (and if lengths tie, then the smallest index) among all words sharing that prefix. While inserting each word (in reversed form) into the Trie, the candidate stored at each node is updated if the current word is a better candidate according to our criteria.

For each query, we reverse it, then traverse the Trie along its characters. We continue as long as children exist matching the characters of the reversed query string. The candidate stored at the deepest node reached gives us the answer since that node corresponds to the longest common suffix. If at any point a character does not exist in the Trie, we stop and use the candidate from the last valid node (or the root if no characters match). This ensures we are returning the index of the word from wordsContainer that has the longest common suffix with the query, with tie-breaking handled by the candidate stored at each node.

Code Solutions

# Python solution using a Trie built from reversed words.

class TrieNode:
    def __init__(self):
        # Dictionary mapping character to TrieNode.
        self.children = {}
        # Candidate as a tuple: (word_length, index) for the best word passing through this node.
        self.candidate = None

class Trie:
    def __init__(self):
        # Initialize the Trie with a root node.
        self.root = TrieNode()
    
    def insert(self, word, word_index):
        # Insert a word (reversed) into the Trie.
        current = self.root
        # Candidate tuple from a word:
        candidate = (len(word), word_index)
        # Update the candidate at the root if needed.
        if current.candidate is None or candidate < current.candidate:
            current.candidate = candidate
        # Process each character in the reversed word.
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
            # Update candidate for this Trie node.
            if current.candidate is None or candidate < current.candidate:
                current.candidate = candidate

    def query(self, rev_query):
        # Perform a query: traverse as far as possible with rev_query.
        current = self.root
        # Start with the candidate at the root (common suffix = empty).
        result_candidate = current.candidate
        for char in rev_query:
            if char in current.children:
                current = current.children[char]
                result_candidate = current.candidate
            else:
                # No further match in Trie; break.
                break
        return result_candidate[1]  # Return the stored index from candidate.

def longestCommonSuffixQueries(wordsContainer, wordsQuery):
    # Build the Trie with reversed words from wordsContainer.
    trie = Trie()
    for idx, word in enumerate(wordsContainer):
        # Reverse each word for suffix matching.
        reversed_word = word[::-1]
        trie.insert(reversed_word, idx)
    
    # For each query, reverse it and get the candidate.
    result = []
    for query in wordsQuery:
        reversed_query = query[::-1]
        selected_index = trie.query(reversed_query)
        result.append(selected_index)
    return result

# Example usage:
if __name__ == '__main__':
    wordsContainer = ["abcd", "bcd", "xbcd"]
    wordsQuery = ["cd", "bcd", "xyz"]
    print(longestCommonSuffixQueries(wordsContainer, wordsQuery))
    # Expected output: [1, 1, 1]
← Back to All Questions