Show problems as
Classic problem #3076MediumArrayHash TableStringTrie

Shortest Uncommon Substring in an Array

Real-world version: Unique Fragment Per Code
Tracked in this browser only
Read Shortest Uncommon Substring in an Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A warehouse labels every bin with a lowercase part code. The picking sheet wants, for each code, a short fragment that identifies it unambiguously.

You are given codes, an array of n part codes. A fragment of a code is any contiguous run of its characters. For each index i, report the shortest fragment of codes[i] that appears in no other code of the array -- appearing anywhere inside another code disqualifies it. When several fragments tie for shortest, report the alphabetically smallest of them. When no fragment of codes[i] qualifies, report the empty string for that index.

Return an array answer where answer[i] is the fragment reported for codes[i].

Examples

Example 1

Input
codes = ["cab", "xyz"]
Output
["a", "x"]

For "cab" the fragments "a", "b" and "c" each fail to appear in "xyz", and "a" is the alphabetically smallest of them. For "xyz" the single characters all qualify, and "x" is alphabetically smallest.

Example 2

Input
codes = ["ab", "ax"]
Output
["b", "x"]

The fragment "a" appears in both codes, so it qualifies for neither. "b" appears only in the first code and "x" only in the second.

Example 3

Input
codes = ["abc", "abc"]
Output
["", ""]

The two codes are identical, so every fragment of one appears in the other and both indices report the empty string.

Example 4

Input
codes = ["zz", "z"]
Output
["zz", ""]

For the first code, "z" appears in the second code but "zz" does not. The second code has only the fragment "z", which appears in the first code.

Constraints

  • n == codes.length
  • 2 <= n <= 100
  • 1 <= codes[i].length <= 20
  • codes[i] consists of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_substrings(codes: list[str]) -> list[str]:
Java
public String[] shortestSubstrings(String[] codes)

More on the same topics