Container Indices for Longest Shared Suffixes
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Container Indices for Longest Shared Suffixes
You are given two string arrays, `wordsContainer` and `wordsQuery`.
For every query string, choose one string from `wordsContainer` using these priorities, in order:
1. Maximize the length of the common suffix shared with the query.
2. Among strings tied on that suffix length, choose the shortest complete container string.
3. If their complete lengths also tie, choose the smallest index in `wordsContainer`.
Return the chosen zero-based container index for each query, in query order. A suffix is a contiguous ending portion of a string. If no nonempty suffix is shared, the empty suffix has length zero and the same tie rules still apply.
### Examples
**Example 1**
```text
Input: wordsContainer = ["moon","spoon","noon","on"], wordsQuery = ["cartoon","on","cat"]
Output: [0,3,3]
```
For `"cartoon"`, the first three container strings share the suffix `"oon"`. `"moon"` and `"noon"` tie for shortest complete length among them, so index zero wins. The shorter word `"on"` shares only two ending characters and loses on the first priority.
For query `"on"`, every container shares its two-character suffix; the complete word `"on"` is shortest. For `"cat"`, none shares its final character, so the shortest container word wins through the empty-suffix case. Both answers are index three.
**Example 2**
```text
Input: wordsContainer = ["abc","xbc","bc","bc"], wordsQuery = ["zabc","ybc","zz"]
Output: [0,2,2]
```
`"zabc"` shares the three-character suffix `"abc"` only with index zero. For `"ybc"`, all containers share `"bc"`; indices two and three have the shortest complete length, and index two is earlier. For `"zz"`, no nonempty suffix is shared, and that same shortest-length, earliest-index choice applies.
### Constraints
- `1 <= wordsContainer.length, wordsQuery.length <= 10^4`.
- `1 <= wordsContainer[i].length <= 5 * 10^3`.
- `1 <= wordsQuery[i].length <= 5 * 10^3`.
- Both arrays contain only strings of lowercase English letters.
- The sum of the lengths of all strings in `wordsContainer` is at most `5 * 10^5`.
- The sum of the lengths of all strings in `wordsQuery` is at most `5 * 10^5`.
### Clarifying Questions
- Does a shorter container word beat a longer suffix match? No; common-suffix length is the first priority.
- Is the returned value a suffix length or a container index? It is the container index.
- Can duplicate container strings occur? Yes; no uniqueness guarantee is given, and an exact tie goes to the earlier index.
- Can the empty suffix be the best shared suffix? Yes; choose the shortest container string, then the earliest index.
- Are queries independent? Yes; answering one does not remove or change any container string.
### C++ Interface
```cpp
class Solution {
public:
vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
}
};
```
### Reasoning Checkpoints
- Apply suffix length, complete word length and container index in the specified priority order.
- Handle equal strings and the empty-suffix case while preserving query output order.
- Justify correctness and resource use under both total-character bounds.
```hint Organize strings from their last character
A common suffix becomes a common prefix when characters are read backward. Store container strings in a trie from right to left, and retain the best length/index choice at each node, including the root.
```
Overview: Choose a container index for each query by longest common suffix, then shortest complete word, then earliest original index.
