Highlight the Shortest Unique Substring in Each Label

Problem Statement

In a dropdown menu component, keyboard navigation shortcuts are displayed by highlighting a trigger character sequence inside each item's label. To avoid user confusion, each shortcut sequence must be unique across all available labels.

Given a list of strings labels, transform each label by enclosing its shortest unique substring inside square brackets [ and ].

A substring of labels[i] is considered unique if its lowercase version does not appear as a substring in the lowercase version of any other labels[j] (where j != i).

Follow these rules for each label:

1. Choose the shortest unique substring.
2. If there is a tie in length, choose the one with the earliest starting index.
3. The uniqueness check is case-insensitive, but the final output must preserve the original casing of labels[i].
4. If no unique substring exists for a label, leave the label unchanged.

Function Signature

def highlight_shortcuts(labels: list[str]) -> list[str]:
    pass

Constraints

• 1 <= len(labels) <= 100
• 1 <= len(label) <= 50 for each label in labels
• Labels consist of English letters, digits, and spaces.

Examples

Example 1

Input: labels = ["apple", "banana", "cat"]
Output: ["a[p]ple", "[b]anana", "[c]at"]

Explanation:

• For "apple": 'a' appears in "banana" and "cat". The next character 'p' (index 1) does not appear in any other label. It has length 1, which is optimal, resulting in "a[p]ple".
• For "banana": 'b' (index 0) is not in "apple" or "cat", resulting in "[b]anana".
• For "cat": 'c' (index 0) is not in "apple" or "banana", resulting in "[c]at".

Example 2

Input: labels = ["pull", "push", "pullet"]
Output: ["pull", "pu[s]h", "pull[e]t"]

Explanation:

• For "pull": Every substring of "pull" (including the full word itself) appears inside "pullet". Hence, no unique substring exists, and it remains unchanged.
• For "push": 'p' and 'u' appear in "pull" and "pullet". 's' (index 2) is unique and has length 1, resulting in "pu[s]h".
• For "pullet": Substrings of length 1: 'p', 'u', 'l' appear in "pull". 'e' (index 4) is unique, resulting in "pull[e]t".

Example 3

Input: labels = ["File", "FILTER"]
Output: ["[File]", "F[ILT]ER"]

Explanation:

• "file" is a prefix of "filter" (case-insensitively). Thus, "f", "fi", and "fil" appear in both. "File" cannot be shortened uniquely, but the full string "File" is unique because "FILTER" does not contain "e" followed by nothing. Wait, "filter" has 'e', but "file" has 'l' then 'e'. The shortest unique substring in "File" is "le"? No: "fil" is in "filter", but "le" is not in "filter". "le" has length 2 and starts at index 2 ("Fi[le]"). However, between "File" and "FILTER", "FILT" is not in "File". The exact tie-breaks depend on length first.