You are given two arrays of strings, wordsContainer and wordsQuery.

For each string wordsQuery[i], find the string in wordsContainer that shares the longest common suffix with it.

• If multiple strings in wordsContainer share the same longest suffix, choose the one with the smallest length.

• If two or more such strings have the same smallest length, choose the string that appears earliest in wordsContainer.

Return an array of integers ans, where ans[i] is the index of the chosen string in wordsContainer for the query wordsQuery[i].

Constraints:

• $1 \leq$ wordsContainer.length, wordsQuery.length $\leq 10^4$

• $1 \leq$ wordsContainer[i].length $\leq 5 * 10^3$

• $1 \leq$ wordsQuery[i].length $\leq 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$.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.