A Piece Only One Word Has

Medium

You are given a list of non-empty strings labels. For each string labels[i], find its shortest substring (a contiguous piece) that does **not occur** in any other string of the list. If several such substrings share the minimal length, take the lexicographically smallest one. If no such substring exists at all, the answer for that string is an empty string. Return the list of answers, one per string, in the same order as labels.

Example 1

labels=["milk", "silk", "mint"] → ['mil', 's', 'n']

Every single letter of "milk" appears elsewhere, and so do "mi", "il" and "lk"; "mil" is the shortest piece only it has. "silk" has the unique letter "s". "mint" has "n" and "t", and "n" comes first.

Example 2

labels=["ab", "abc"] → ['', 'c']

Everything in "ab" also appears in "abc", so its answer is empty. "abc" owns the letter "c".

Example 3

labels=["aa", "aa"] → ['', '']

The two labels are identical, so neither has a piece of its own.

Constraints

2 ≤ len(labels) ≤ 100
1 ≤ len(labels[i]) ≤ 20
The strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Array Hash Table String

Similar problems

Split Into Dictionary Words Medium Highlight Search Hits Medium Shorten Words to Their Roots Medium Most Searched Words Medium Word Grown Letter by Letter Medium

Input

labels=["milk", "silk", "mint"]

Expected

['mil', 's', 'n']

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.