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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Common Suffix Queries

Difficulty: Hard

Problem Description

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].

Key Insights

  • The problem requires finding the longest common suffix for each query against a list of words.
  • If there are ties in the length of the longest common suffix, the word with the smallest length should be chosen.
  • If there are still ties, the word that appears first in the wordsContainer should be selected.
  • Efficient string comparison is crucial given the constraints on length and number of queries.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of wordsContainer and m is the average length of the strings in wordsQuery.
Space Complexity: O(1) - we use a constant amount of space for counting suffix lengths and tracking indices.

Solution

To solve this problem, we will iterate over each string in wordsQuery and compare it with each string in wordsContainer to find the longest common suffix. We will keep track of the maximum suffix length found and the corresponding index of the string from wordsContainer. If we find a new maximum suffix length, we update our result. If there is a tie, we will check the length of the strings and update accordingly. Finally, we'll build the result array to return the indices.

Code Solutions

def longestCommonSuffixQueries(wordsContainer, wordsQuery):
    def longest_common_suffix(s1, s2):
        min_length = min(len(s1), len(s2))
        length = 0
        for i in range(1, min_length + 1):
            if s1[-i] == s2[-i]:
                length += 1
            else:
                break
        return length

    results = []
    for query in wordsQuery:
        max_suffix_length = -1
        best_index = -1
        for i, word in enumerate(wordsContainer):
            suffix_length = longest_common_suffix(word, query)
            if (suffix_length > max_suffix_length or
                (suffix_length == max_suffix_length and (best_index == -1 or len(word) < len(wordsContainer[best_index])))):
                max_suffix_length = suffix_length
                best_index = i
        results.append(best_index)
    return results
← Back to All Questions