Shortest Substring of Each String That Appears in No Other String
Company: Moveworks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array of strings. For each string, find its shortest substring that does not occur in any other string of the array. The Rules below settle ties and strings that have no such substring. In the reported round, a brute-force solution that passed every test case was followed by a short discussion of how to make it faster.
### Function Signature
```python
def shortest_unique_substrings(strings: list[str]) -> list[str]:
```
### Rules
- A substring is a contiguous, non-empty run of characters of a string.
- For index `i`, a substring `t` of `strings[i]` qualifies when `t` is not a substring of `strings[j]` for any index `j != i`. How often `t` occurs inside `strings[i]` itself does not matter.
- `answer[i]` is the shortest qualifying substring of `strings[i]`. If several qualifying substrings have that shortest length, `answer[i]` is the lexicographically smallest of them.
- If no substring of `strings[i]` qualifies, `answer[i]` is the empty string `""`.
- Equal strings at different indices are separate entries: every substring of one occurs in the other, so each of them gets `""`.
- Return a list with one answer per input string, in input order.
### Constraints
- `1 <= len(strings) <= 100`
- `1 <= len(strings[i]) <= 20`
- Every string contains only lowercase English letters `a` to `z`.
### Examples
**Example 1**
```text
Input: strings = ["apple", "apply", "ape"]
Output: ["le", "y", "pe"]
```
Every single letter of `"apple"` occurs in `"apply"` or `"ape"`, and of its two-letter substrings `"ap"`, `"pp"`, `"pl"` and `"le"`, only `"le"` occurs in neither. In `"apply"`, the letter `"y"` occurs nowhere else. Every letter of `"ape"` occurs in `"apple"`, `"ap"` occurs in both other strings, and `"pe"` occurs in neither.
**Example 2**
```text
Input: strings = ["abc", "abc", "bcde"]
Output: ["", "", "d"]
```
The two copies of `"abc"` contain each other's substrings, so both answers are empty. In `"bcde"`, both `"d"` and `"e"` are absent from the other strings; `"d"` is lexicographically smaller.
**Example 3**
```text
Input: strings = ["ab", "ba", "aba"]
Output: ["", "", "aba"]
```
Every substring of `"ab"` and of `"ba"` occurs in `"aba"`. Every substring of `"aba"` shorter than the whole string occurs in `"ab"` or `"ba"`, so its answer is the whole string.
Overview: Given an array of lowercase strings, return for each string its shortest substring that occurs in no other string of the array, breaking ties lexicographically and returning an empty string when none exists. The problem tests substring enumeration, fast membership checks across strings and careful handling of duplicate strings.
You are given a list of strings `strings`. For each string, find its shortest substring that does not occur in any other string of the list.
Rules:
- A substring is a contiguous, non-empty run of characters of a string.
- For index `i`, a substring `t` of `strings[i]` qualifies when `t` is not a substring of `strings[j]` for any index `j != i`. How often `t` occurs inside `strings[i]` itself does not matter.
- `answer[i]` is the shortest qualifying substring of `strings[i]`. If several qualifying substrings have that shortest length, `answer[i]` is the lexicographically smallest of them.
- If no substring of `strings[i]` qualifies, `answer[i]` is the empty string `""`.
- Equal strings at different indices are separate entries: every substring of one occurs in the other, so each of them gets `""`.
Return a list with exactly one answer per input string, in input order.
Example 1:
Input: strings = ["apple", "apply", "ape"]
Output: ["le", "y", "pe"]
Explanation: Every single letter of "apple" occurs in "apply" or "ape", and of its two-letter substrings "ap", "pp", "pl" and "le", only "le" occurs in neither. In "apply", the letter "y" occurs nowhere else. Every letter of "ape" occurs in "apple", "ap" occurs in both other strings, and "pe" occurs in neither.
Example 2:
Input: strings = ["abc", "abc", "bcde"]
Output: ["", "", "d"]
Explanation: The two copies of "abc" contain each other's substrings, so both answers are empty. In "bcde", both "d" and "e" are absent from the other strings; "d" is lexicographically smaller.
Constraints:
- 1 <= len(strings) <= 100
- 1 <= len(strings[i]) <= 20
- Every string contains only lowercase English letters 'a' to 'z'.
Constraints
- 1 <= len(strings) <= 100
- 1 <= len(strings[i]) <= 20
- Every string contains only lowercase English letters 'a' to 'z'.
Examples
Input: (['apple', 'apply', 'ape'],)
Expected Output: ['le', 'y', 'pe']
Explanation: Source Example 1: every letter of 'apple' occurs elsewhere and 'le' is its only two-letter substring found nowhere else; 'y' is unique to 'apply'; 'pe' is the first unique substring of 'ape'.
Input: (['abc', 'abc', 'bcde'],)
Expected Output: ['', '', 'd']
Explanation: Source Example 2: equal strings at different indices both get ''; in 'bcde' both 'd' and 'e' qualify and the lexicographically smaller 'd' wins.
Hints
- A string of length at most 20 has at most 210 substrings, so considering all of them is affordable.
- Whether a substring qualifies depends only on whether some other index contains it, never on how many times it repeats inside its own string.
- Consider candidate lengths from shortest to longest: once some length has a qualifying substring, no longer substring can be the answer.