Shortest Uncommon Substring in an Array — Problem & Solution
Shortest Uncommon Substring in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Shortest Uncommon Substring in an Array is a medium coding problem on arrays, strings and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Trie
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array arr of n non-empty strings of lowercase letters.
Build an array answer of size n where answer[i] is the shortest substring of arr[i] that does not occur as a substring of any other string in arr. If several substrings of that shortest length qualify, take the lexicographically smallest one. If no substring of arr[i] qualifies, answer[i] is the empty string.
Return answer.
Example 1
Input: arr = ["cab","ad","bad","c"]
Output: ["ab","","ba",""]
Explanation: Every single letter of "cab" appears elsewhere; of its length-2 substrings "ab" and "ca", "ab" is unused elsewhere and smaller. Every substring of "ad" appears in "bad". For "bad", "ba" is the shortest unused one. "c" appears in "cab".
Example 2
Input: arr = ["abc","bcd","abcd"]
Output: ["","","abcd"]
Explanation: Every substring of "abc" and of "bcd" occurs inside "abcd"; only "abcd" itself is unique to the third string.
Example 3
Input: arr = ["zz","zz"]
Output: ["",""]
Explanation: Two identical strings share every substring.
Constraints
2 <= n == arr.length <= 1001 <= arr[i].length <= 20arr[i] consists only of lowercase English letters
Hints for Shortest Uncommon Substring in an Array
Hint 1
Each string has at most
20 * 21 / 2 = 210substrings, so you can afford to try them all.Hint 2
Try lengths in increasing order; for a fixed length, consider the candidates in lexicographic order so the first one that works is the answer.
Hint 3
A candidate works when no other string contains it. Remember to skip the string itself — and that a duplicate of
arr[i]elsewhere blocks everything.
How to solve Shortest Uncommon Substring in an Array
The strings are tiny, so the answer can be found by direct search: try every substring of arr[i] from shortest to longest, lexicographically within a length, and stop at the first one no other string contains.
Approach
- For each index
iand each lengthlen = 1 .. arr[i].length: - among the substrings of
arr[i]of that length, keep the lexicographically smallest one that is not contained in anyarr[j]withj != i; - if one was found, that is
answer[i]— move on to the nexti. - If no length produced one,
answer[i]is"".
Why it works
Lengths are tried in increasing order, so the first length with a qualifying substring is the shortest possible; within it the smallest qualifying candidate is chosen, which is exactly the tie-break the statement demands.
Complexity
- Time —
O(n^2 * L^3) with L <= 20 (each of ~L^2 candidates checked against n strings in O(L^2)) - Space —
O(L)
Pitfalls
- Do not test the candidate against
arr[i]itself — it always occurs there. - Compare candidates only within the same length; the shortest length wins even if a longer substring is lexicographically smaller.
- Identical strings make each other's answers empty.
Reference solution
Python
from typing import List
def shortestSubstrings(arr: List[str]) -> List[str]:
n = len(arr)
res = []
for i, s in enumerate(arr):
ans = ""
for length in range(1, len(s) + 1):
best = None
for st in range(len(s) - length + 1):
t = s[st:st + length]
if best is not None and t >= best:
continue
if all(j == i or t not in arr[j] for j in range(n)):
best = t
if best is not None:
ans = best
break
res.append(ans)
return resJava
public static String[] shortestSubstrings(String[] arr) {
int n = arr.length;
String[] res = new String[n];
for (int i = 0; i < n; i++) {
String s = arr[i], ans = "";
for (int len = 1; len <= s.length(); len++) {
String best = null;
for (int st = 0; st + len <= s.length(); st++) {
String t = s.substring(st, st + len);
if (best != null && t.compareTo(best) >= 0) continue;
boolean unique = true;
for (int j = 0; j < n; j++) {
if (j != i && arr[j].contains(t)) { unique = false; break; }
}
if (unique) best = t;
}
if (best != null) { ans = best; break; }
}
res[i] = ans;
}
return res;
}C++
vector<string> shortestSubstrings(vector<string>& arr) {
int n = arr.size();
vector<string> res(n);
for (int i = 0; i < n; i++) {
const string& s = arr[i];
string ans;
for (int len = 1; len <= (int) s.size(); len++) {
string best;
bool found = false;
for (int st = 0; st + len <= (int) s.size(); st++) {
string t = s.substr(st, len);
if (found && t >= best) continue;
bool unique = true;
for (int j = 0; j < n; j++) {
if (j != i && arr[j].find(t) != string::npos) { unique = false; break; }
}
if (unique) { best = t; found = true; }
}
if (found) { ans = best; break; }
}
res[i] = ans;
}
return res;
}JavaScript
var shortestSubstrings = function(arr) {
var n = arr.length, res = [];
for (var i = 0; i < n; i++) {
var s = arr[i], ans = "";
for (var len = 1; len <= s.length; len++) {
var best = null;
for (var st = 0; st + len <= s.length; st++) {
var t = s.substring(st, st + len);
if (best !== null && t >= best) continue;
var unique = true;
for (var j = 0; j < n; j++) {
if (j !== i && arr[j].indexOf(t) >= 0) { unique = false; break; }
}
if (unique) best = t;
}
if (best !== null) { ans = best; break; }
}
res.push(ans);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.