Find shortest unique substring per word

Shortest unique substring for each word

You are given an array of distinct strings words.

For each word w in words, find a non-empty contiguous substring of w that does not appear as a substring in any other word in the array.

Return, for every word, the shortest such substring.

Tie-breaking

If a word has multiple valid substrings with the same minimal length:

1. Choose the one with the smallest starting index in the word.
2. If there is still a tie, choose the lexicographically smallest substring.

You may assume that for every word, at least one such substring exists.

Example

Input:

['cheapair', 'cheapoair', 'peloton', 'pelican']

Output:

{
  'cheapair': 'pa',
  'cheapoair': 'po',
  'peloton': 't',
  'pelican': 'li'
}

Constraints (typical interview ranges)

• 1 <= len(words) <= 2e3
• 1 <= len(words[i]) <= 2e3
• Total characters across all words <= 2e4
• Lowercase English letters (you may generalize if desired)