3093. Longest Common Suffix Queries LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3093. Longest Common Suffix Queries LeetCode Solution with the best time and space complexity. The solution to Longest Common Suffix Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Common Suffix Queries solution in C++
Longest Common Suffix Queries solution in Java
Longest Common Suffix Queries solution in Python
Additional Resources

3093. Longest Common Suffix Queries LeetCode Solution image

Problem Statement of Longest Common Suffix Queries

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 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 <= 104
1 <= wordsContainer[i].length <= 5 * 103
1 <= wordsQuery[i].length <= 5 * 103
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 * 105.
Sum of wordsQuery[i].length is at most 5 * 105.

Complexity Analysis

Time Complexity: O(\Sigma |\texttt{wordsContainer[i]}| + \Sigma |\texttt{wordsQuery[i]}|)
Space Complexity: O(\Sigma |\texttt{wordsContainer[i]}| + |\texttt{wordsQuery}|)

3093. Longest Common Suffix Queries LeetCode Solution in C++

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  TrieNode() : children(26) {}
  int length = INT_MAX;
  int index = -1;
};

class Solution {
 public:
  vector<int> stringIndices(vector<string>& wordsContainer,
                            vector<string>& wordsQuery) {
    vector<int> ans;
    int minIndex = 0;

    for (int i = 0; i < wordsContainer.size(); ++i) {
      insert(wordsContainer[i], i);
      if (wordsContainer[i].length() < wordsContainer[minIndex].length())
        minIndex = i;
    }

    for (const string& query : wordsQuery) {
      const int index = search(query);
      ans.push_back(index == -1 ? minIndex : index);
    }

    return ans;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  void insert(const string& word, int index) {
    shared_ptr<TrieNode> node = root;
    for (int i = word.length() - 1; i >= 0; --i) {
      const int j = word[i] - 'a';
      if (node->children[j] == nullptr)
        node->children[j] = make_shared<TrieNode>();
      node = node->children[j];
      if (node->length > word.length()) {
        node->length = word.length();
        node->index = index;
      }
    }
  }

  int search(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (int i = word.length() - 1; i >= 0; --i) {
      const int j = word[i] - 'a';
      if (node->children[j] == nullptr)
        return node->index;
      node = node->children[j];
    }
    return node->index;
  }
};
/* code provided by PROGIEZ */

3093. Longest Common Suffix Queries LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public boolean isWord = false;
  public int length = Integer.MAX_VALUE;
  public int index = -1;
}

class Solution {
  public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
    int[] ans = new int[wordsQuery.length];
    int minIndex = 0;

    for (int i = 0; i < wordsContainer.length; ++i) {
      insert(wordsContainer[i], i);
      if (wordsContainer[i].length() < wordsContainer[minIndex].length())
        minIndex = i;
    }

    for (int i = 0; i < wordsQuery.length; ++i) {
      final int index = search(wordsQuery[i]);
      ans[i] = index == -1 ? minIndex : index;
    }

    return ans;
  }

  private TrieNode root = new TrieNode();

  private void insert(final String word, int index) {
    TrieNode node = root;
    for (int i = word.length() - 1; i >= 0; --i) {
      final int j = word.charAt(i) - 'a';
      if (node.children[j] == null)
        node.children[j] = new TrieNode();
      node = node.children[j];
      if (node.length > word.length()) {
        node.length = word.length();
        node.index = index;
      }
    }
  }

  private int search(final String word) {
    TrieNode node = root;
    for (int i = word.length() - 1; i >= 0; --i) {
      final int j = word.charAt(i) - 'a';
      if (node.children[j] == null)
        return node.index;
      node = node.children[j];
    }
    return node.index;
  }
}
// code provided by PROGIEZ

3093. Longest Common Suffix Queries LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}
    self.isWord = False
    self.length = math.inf
    self.index = -1


class Solution:
  def stringIndices(
      self,
      wordsContainer: list[str],
      wordsQuery: list[str],
  ) -> list[int]:
    ans = []
    root = TrieNode()
    minIndex = min(enumerate(wordsContainer), key=lambda x: len(x[1]))[0]

    def insert(word: str, index: int) -> None:
      node = root
      for c in reversed(word):
        node = node.children.setdefault(c, TrieNode())
        if node.length > len(word):
          node.length = len(word)
          node.index = index

    def search(word: str) -> int:
      node = root
      for c in reversed(word):
        if c not in node.children:
          return node.index
        node = node.children[c]
      return node.index

    for i, word in enumerate(wordsContainer):
      insert(word, i)

    for query in wordsQuery:
      index = search(query)
      ans.append(minIndex if index == -1 else index)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents