3076.Shortest_Uncommon_Substring_in_an_Array(Medium).md

3076. Shortest Uncommon Substring in an Array (Medium)

Date and Time: Jun 8, 2026

Link: https://leetcode.com/problems/shortest-uncommon-substring-in-an-array/

Question:

You are given an array arr of size n consisting of non-empty strings.

Find a string array answer of size n such that:

• answer[i] is the shortest substring of arr[i] that does not occur as a substring in any other string in arr. If multiple such substrings exist, answer[i] should be the lexicographically smallest. And if no such substring exists, answer[i] should be an empty string.

Return the array answer.

Example 1:

Input: arr = ["cab","ad","bad","c"]
Output: ["ab","","ba",""]
Explanation:

• "cab": "ab" appears only in "cab" (length 2, lexicographically smallest among unique substrings of length 2).
  
• "ad": all substrings ("a", "d", "ad") also appear in other strings.
  
• "bad": "ba" appears only in "bad".
  
• "c": "c" also appears in "cab", so no unique substring exists.

Example 2:

Input: arr = ["abc","bcd","abcd","d"]
Output: ["bc","cd","abcd","d"]

Constraints:

• n == arr.length

• 2 <= n <= 100

• 1 <= arr[i].length <= 20

• arr[i] consists only of lowercase English letters.

Walk-through:

For each string, generate all its substrings and count how many distinct strings in arr contain each substring. A substring is uncommon if its count equals 1.

1. Use hashmap {substring: count} to track how many strings each substring appears in. Use a seen set per string to avoid counting the same substring twice for the same string.

2. Use combDict {string: set of substrings} to store all substrings per string.

3. For each string, filter its substrings to those with hashmap[sub] == 1, then pick the one with minimum length, breaking ties lexicographically.

Python Solution:

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        # Q: Return smallest substring for each arr[i] with no repetiton in other lists
        # S: For each arr[i], find all the substring combinations, save into hashmap {comb: occurrence}
        # 2. For each arr[i], we have a list of all combinations, narrow down a list with all unique combination, then find the min()

        # Understanding: Every arr[i] substring should only be counted once.
        # lexicographically smallest: compare smallest length first, then compare the chars.

        # TC: O(n*2^k), SC: O(n*2^k)
        # 8mins + 
        hashmap = {}    # {comb: occurrence}
        combDict = collections.defaultdict(set)    # {arr[i]: [all combinations]}
        res = []
        # Double for-loops to handle
        def gen_substring(string, seen):
            for i in range(0, len(string)):
                for j in range(i, len(string)):
                    substring = string[i:j+1]
                    # Save substring into hashmaps, but not in seen before
                    if substring not in seen:
                        seen.add(substring)
                        hashmap[substring] = hashmap.get(substring, 0) + 1
                        combDict[string].add(substring)

        # Find all the substrings
        for lst in arr:
            seen = set()
            gen_substring(lst, seen)
        # Find smallest substring
        for lst in arr:
            tmp = ""
            for comb in combDict[lst]:
                # Append comb into tmp[]
                if comb in hashmap and hashmap[comb] == 1:
                    # Append comb into tmp[], length first
                    if tmp == "" or len(comb) < len(tmp) or (len(comb) == len(tmp) and comb < tmp):
                        tmp = comb
            # Check if we have valid combs in tmp, otherwise, append ""
            res.append(tmp)
        return res

Time Complexity: $O(n \cdot L^2)$, n = len(arr), L = max length of arr[i], generating all substrings per string is $O(L^2)$.
Space Complexity: $O(n \cdot L^2)$, for the hashmap and combDict storing all substrings.