LeetCode 3093: Longest Common Suffix Queries Solution

Master LeetCode problem 3093 (Longest Common Suffix Queries), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3093. Longest Common Suffix Queries

Hard

Array String Trie

Problem Explanation

Explanation

To solve this problem, we can iterate through each query word and for each query word, iterate through all the words in the container to find the word with the longest common suffix. We can maintain a variable to keep track of the index of the word with the longest common suffix for each query word.

For each query word:

Initialize the index of the word with the longest common suffix as -1 and the length of the longest common suffix as 0.
Iterate through all the words in the container.
For each word in the container, find the length of the common suffix with the query word.
If the length of the common suffix is greater than the current longest common suffix length, update the index of the word with the longest common suffix and the length of the longest common suffix.
If the length of the common suffix is equal to the current longest common suffix length, compare the lengths of the words and update the index accordingly.

Finally, return the list of indices of the words with the longest common suffix for each query word.

Time Complexity

Let n be the total number of characters in all wordsContainer and wordsQuery combined.

The time complexity of the solution is O(n^2) because we iterate through each query word and for each query word, we iterate through each word in the container to find the longest common suffix.

Space Complexity

The space complexity of the solution is O(1) as we are using a constant amount of extra space.

Solution Code

class Solution {
    public int[] longestCommonSuffixQueries(String[] wordsContainer, String[] wordsQuery) {
        int[] ans = new int[wordsQuery.length];
        
        for (int i = 0; i < wordsQuery.length; i++) {
            int maxIndex = -1;
            int maxLen = 0;
            
            for (int j = 0; j < wordsContainer.length; j++) {
                int len = 0;
                
                while (len < wordsQuery[i].length() && len < wordsContainer[j].length() && 
                       wordsQuery[i].charAt(wordsQuery[i].length() - 1 - len) == wordsContainer[j].charAt(wordsContainer[j].length() - 1 - len)) {
                    len++;
                }
                
                if (len > maxLen || (len == maxLen && wordsContainer[j].length() < wordsContainer[maxIndex].length())) {
                    maxIndex = j;
                    maxLen = len;
                }
            }
            
            ans[i] = maxIndex;
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3093 (Longest Common Suffix Queries)?

This page provides optimized solutions for LeetCode problem 3093 (Longest Common Suffix Queries) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3093 (Longest Common Suffix Queries)?

The time complexity for LeetCode 3093 (Longest Common Suffix Queries) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3093 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3093 in Java, C++, or Python.

Back to LeetCode Solutions