Shortest Uncommon Substring in an Array - Video Solutions

Problem Overview: Given an array of strings, return the shortest substring of each string that does not appear in any other string in the array. If multiple substrings satisfy the condition, choose the lexicographically smallest one. If none exists, return an empty string for that index.

Approach 1: Brute Force with Substring Check (O(n * m^3) time, O(1) extra space)

Generate every possible substring for each string and check whether that substring appears in any other string in the array. For a string of length m, there are O(m^2) substrings. For each candidate substring, iterate through the remaining n-1 strings and use a substring search operation like find(). This leads to roughly O(n * m^3) complexity in the worst case. While slow, it clearly demonstrates the definition of an "uncommon substring" and is useful for understanding the problem before optimizing. This approach mainly relies on simple string operations and iteration across the array.

Approach 2: Optimized Set / Hash Map Approach (O(n * m^2) time, O(n * m^2) space)

Instead of repeatedly scanning other strings, precompute how often each substring appears across the entire array. For every string, generate all substrings and store them in a set to avoid duplicates within the same string. Insert those substrings into a global hash table that tracks how many different strings contain that substring. After building this frequency map, iterate again through each string's substrings ordered by increasing length and lexicographical order. The first substring with frequency 1 is the answer for that string. This reduces repeated scanning and replaces it with constant‑time hash lookups.

This optimization works because substring uniqueness is determined globally. Once substring frequencies are known, checking whether a substring is unique becomes a simple hash lookup instead of scanning every other string. Substring generation remains O(m^2), which dominates the runtime.

A more advanced variation can store substrings inside a trie or suffix structure, but for typical interview constraints the hash‑set approach is simpler and performs well.

Recommended for interviews: Start by explaining the brute force idea since it directly models the problem definition. Then move to the optimized hash‑map approach that precomputes substring frequencies. Interviewers typically expect the second solution because it reduces repeated work and demonstrates practical use of substring enumeration with hash lookups.