MediumArrayHash TableStringTrieUpdated Sep 2026

3076. Shortest Uncommon Substring in an Array

Asked at Airbnb

Difficulty

Medium

Time

O(n * L^3)

Space

O(n * L^2)

Pattern

Array

Companies

1

Problem

You are given an array arr of non-empty strings. For each string arr[i], you must find the shortest substring of arr[i] that does not appear as a substring in any of the other strings in the array.

If several substrings of that shortest length qualify, pick the lexicographically smallest one. If no substring of arr[i] is unique to it, the answer for that position is an empty string "".

Return an array answer of the same length as arr, where answer[i] is the chosen substring for arr[i] (or ""). Note that a substring must be contiguous — you cannot skip characters.

Find the shortest unique substring

arr[0] = "cab"cab012Length-1 substrings c, a, b all appear in otherstrings, so none works.length-2 substringscaab01Both "ca" and "ab" are unique, and "ab" islexicographically smaller, so the answer is "ab".
For "cab", length-1 substrings are shared, but length-2 substrings "ca" and "ab" are unique, so we pick the smaller one.

Constraints

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

Examples

Example 1
Inputarr = ["cab","ad","bad","c"]
Output["ab","","ba",""]
WhyFor "cab", the length-1 substrings c, a, b all appear in other strings, but the length-2 substrings "ca" and "ab" are unique; "ab" is lexicographically smaller. For "ad", every substring (a, d, ad) also appears elsewhere, so the answer is empty. For "bad", "ba" is a unique length-2 substring. For "c
Example 2
Inputarr = ["abc","bcd","abcd"]
Output["","","abcd"]
WhyEvery substring of "abc" (a, b, c, ab, bc, abc) also appears in "abcd", so it has no answer. The same holds for "bcd". For "abcd", the only substring not found in the other two strings is the whole string "abcd".

Asked At

1 companies
CompanyDifficulty
AirbnbMediumView all Airbnb questions →

How to Think About It

1

Each string has at most 20 * 21 / 2 = 210 substrings, so enumerating them is cheap.

2

Precompute, for every string, the set of all its substrings.

3

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.

4

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.

5

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²).

Count each substring across all strings

count of substringssubstringstrings containing itc2a2b2ca1ab1ba1Substrings with count 1 are unique to one string; count 2 meansshared.for each string, list substringscount how many strings contain each substrintry lengths 1, 2, ... and keep count == 1 capick lexicographically smallest, else emptyThe first length that yields any unique substring gives the answerfor that string.answer[i] = min{ t : t is substring of arr[i], count[t] == 1 }shortest length first, then smallest alphabetically
A substring is uncommon for string i exactly when its global count is 1.
ComplexityTime O(n * L^3)Space O(n * L^2)Building all substrings of every string costs O(n * L^2) substrings, and each substring of length up to L is copied in O(L) time; L = 20 here.

What Trips People Up in Real Interviews

1

Counting substring occurrences instead of the number of different strings containing them. A substring repeated inside one string is still uncommon.

2

Returning the first uncommon substring found instead of the lexicographically smallest of the shortest ones.

3

Checking against other strings with in on raw strings for every candidate — works, but precomputed sets are cleaner.

4

Forgetting the empty-string answer when no uncommon substring exists.

Solution Code

O(n * L^3) time
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 res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n * L^3) time and O(n * L^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.