Shortest Uncommon Substring in an Array
Asked at Airbnb
Problem
Shortest Uncommon Substring in an Array asks, for each string, for its shortest substring that does not appear in any other string in the array (lexicographically smallest on ties, or empty if none exists). With at most 100 strings of length 20, precomputing substring sets and brute-forcing is the intended solution.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Medium | View all Airbnb questions → |
How to Think About It
Each string has at most 20 * 21 / 2 = 210 substrings, so enumerating them is cheap.
Precompute, for every string, the set of all its substrings.
For string i, try substring lengths from 1 upward. For each length, collect its substrings of that length that are absent from every other string's set, and take the lexicographically smallest. The first length with any candidate gives the answer.
Alternatively, count in how many different strings each substring occurs (a global map from substring to number of strings containing it). A substring of string i is uncommon iff its count is 1.
Walkthrough: ["cab","ad","bad","c"]: "cab" -> length-2 candidates "ca" (unique) and "ab" (unique) -> "ab". "ad" -> none. "bad" -> "ba". "c" -> none.
Optimal Approach
Step 1: For each string, build the set of its distinct substrings; count, for each substring, how many strings contain it.
Step 2: For each string s:
For length from 1 to len(s):
cands = sorted(sub for sub of that length in s if count[sub] == 1).
If cands, answer is cands[0]; stop.
Otherwise the answer is "".
Step 3: Return the answers.
Time: O(n * L³) with L = 20 (substring building dominates). Space: O(n * L²).
What Trips People Up in Real Interviews
Counting substring occurrences instead of the number of different strings containing them. A substring repeated inside one string is still uncommon.
Returning the first uncommon substring found instead of the lexicographically smallest of the shortest ones.
Checking against other strings with in on raw strings for every candidate — works, but precomputed sets are cleaner.
Forgetting the empty-string answer when no uncommon substring exists.
Solution Code
def shortestSubstrings(arr):
subs = []
count = {}
for s in arr:
cur = {s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)}
subs.append(cur)
for t in cur:
count[t] = count.get(t, 0) + 1
res = []
for s in arr:
ans = ''
for length in range(1, len(s) + 1):
cands = sorted(s[i:i + length] for i in range(len(s) - length + 1)
if count[s[i:i + length]] == 1)
if cands:
ans = cands[0]
break
res.append(ans)
return resFrequently Asked Questions
What is the Shortest Uncommon Substring in an Array problem?
Shortest Uncommon Substring in an Array asks, for each string, for its shortest substring that does not appear in any other string in the array (lexicographically smallest on ties, or empty if none exists). With at most 100 strings of length 20, precomputing substring sets and brute-forcing is the intended solution.
How do you solve Shortest Uncommon Substring in an Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shortest Uncommon Substring in an Array?
Shortest Uncommon Substring in an Array is asked at Airbnb. It is a medium difficulty problem.
What are common mistakes on Shortest Uncommon Substring in an Array?
- Counting substring occurrences instead of the number of different strings containing them. A substring repeated inside one string is still uncommon.
- Returning the first uncommon substring found instead of the lexicographically smallest of the shortest ones.
- Checking against other strings with `in` on raw strings for every candidate — works, but precomputed sets are cleaner.
- Forgetting the empty-string answer when no uncommon substring exists.