Shortest Uncommon Substring in an Array solution and explanation
9 more videos on this problem
Shortest Uncommon Substring in an Array | Detailed Intuition | Dry Run | Leetcode 3076 | Contest 388codestorywithMIK · 40:09 · 4K views
3076. Shortest Uncommon Substring in an Array | Implementation | Time Complexity AnalysisAryan Mittal · 25:13 · 3K views
3076 Shortest Uncommon Substring in an Array || Brute Force to Optimal 🔥 || Time: 10^5 ✅Ayush Rao · 15:44 · 2K views
3076. Shortest Uncommon Substring in an Array (Leetcode Medium)Programming Live with Larry · 20:14 · 681 views
3076. Shortest Uncommon Substring in an Array | LEETCODE WEEKLY 388code Explainer · 10:18 · 583 views
Shortest Uncommon Substring in an Array Question | Weekly Contest 388CodeWithMe21 · 0:38 · 450 views
LeetCode 3076 - Shortest Uncommon Substring in an Array - PythonAlpha-Code · 27:49 · 431 views
100251. Shortest Uncommon Substring in an Array | leetcode weekly-contest-388 | leetcode today answesilent coder · 0:39 · 388 views
LeetCode | 3076. Shortest Uncommon Substring in an Array | Medium | Weekly Contest 388Coding with Bobby · 10:44 · 307 views
100251 Shortest Uncommon Substring in an Array|| leetcode || contest 388 || solved || javaSsquare · 1:09 · 255 views
The problem
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 ofarr[i]that does not occur as a substring in any other string inarr. 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: We have the following: - For the string "cab", the shortest substring that does not occur in any other string is either "ca" or "ab", we choose the lexicographically smaller substring, which is "ab". - For the string "ad", there is no substring that does not occur in any other string. - For the string "bad", the shortest substring that does not occur in any other string is "ba". - For the string "c", there is no substring that does not occur in any other string.
Example 2:
Input: arr = ["abc","bcd","abcd"] Output: ["","","abcd"] Explanation: We have the following: - For the string "abc", there is no substring that does not occur in any other string. - For the string "bcd", there is no substring that does not occur in any other string. - For the string "abcd", the shortest substring that does not occur in any other string is "abcd".
Constraints:
n == arr.length2 <= n <= 1001 <= arr[i].length <= 20arr[i]consists only of lowercase English letters.
Approach overview
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.
Approach 1: Brute Force Approach with Substring Check
This approach involves generating all possible substrings for each string in arr and checking if each substring appears in any other string in arr. We keep track of the shortest substring for each string that does not appear in any of the other strings. To ensure the result is the lexicographically smallest substring when two are of equal length, sort the substrings and select the first valid one.
def shortest_uncommon_substring(arr):
def get_substrings(s):
subs = []
for start in range(len(s)):
for end in range(start + 1, len(s) + 1):
subs.append(s[start:end])
return subs
def is_unique(sub, index, arr):
for i, other in enumerate(arr):
if i != index and sub in other:
return False
return True
result = []
for i, s in enumerate(arr):
substrings = get_substrings(s)
substrings.sort() # This sorts substrings lexicographically
found = ''
for sub in substrings:
if is_unique(sub, i, arr):
found = sub
break
result.append(found)
return result
# Example Usage
arr = ["cab","ad","bad","c"]
print(shortest_uncommon_substring(arr)) # Output: ['ab', '', 'ba', '']import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ShortestUncommonSubstring {
public static List<String> shortestUncommonSubstring(String[] arr) {
List<String> result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
String found = findUniqueSubstring(arr, i);
result.add(found);
}
return result;
}
private static String findUniqueSubstring(String[] arr, int index) {
String s = arr[index];
List<String> substrings = new ArrayList<>();
for (int start = 0; start < s.length(); start++) {
for (int end = start + 1; end <= s.length(); end++) {
substrings.add(s.substring(start, end));
}
}
Collections.sort(substrings);
for (String sub : substrings) {
if (isUnique(sub, index, arr)) {
return sub;
}
}
return "";
}
private static boolean isUnique(String sub, int index, String[] arr) {
for (int i = 0; i < arr.length; i++) {
if (i != index && arr[i].contains(sub)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] arr = {"cab", "ad", "bad", "c"};
System.out.println(shortestUncommonSubstring(arr)); // Output: [ab, , ba, ]
}
}This Python function finds the shortest unique substring for each in the array. It first generates all possible substrings for a given string and checks if they appear in any other string, ensuring it also accounts for lexicographical order by sorting the substrings. The function get_substrings generates all possible substrings, and the function is_unique determines if a substring is unique across other strings in the array.
Time Complexity: O(n * m^3) where n is the number of strings and m is the maximal length of the strings. We generate all substrings of a string, which is O(m^2), and then for each substring check it against other strings which is another O(n*m) check.
Space Complexity: O(n * m) due to storage of substrings, assuming the worst case.
Approach 2: Optimized Set Approach
Instead of iterating through all substrings, we can use sets to store already seen substrings for each string. We compare for uniqueness by checking each substring against combined sets of other strings. This can be implemented using hash maps to store substrings to avoid overlaps efficiently. We also keep track of the first occurrence of a substring length-wise to ensure the answer is lexicographically smallest when possible.
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <algorithm>
std::vector<std::string> shortestUncommonSubstring(std::vector<std::string>& arr) {
std::vector<std::string> result(arr.size(), "");
for (int i = 0; i < arr.size(); ++i) {
std::unordered_set<std::string> comprehensiveSet;
for (int j = 0; j < arr.size(); ++j) {
if (i != j) {
const std::string& s = arr[j];
for (size_t start = 0; start < s.size(); ++start) {
for (size_t end = start + 1; end <= s.size(); ++end) {
comprehensiveSet.insert(s.substr(start, end - start));
}
}
}
}
const std::string& s1 = arr[i];
std::string minSubstring = "";
for (size_t start = 0; start < s1.size(); ++start) {
for (size_t end = start + 1; end <= s1.size(); ++end) {
std::string sub = s1.substr(start, end - start);
if (comprehensiveSet.find(sub) == comprehensiveSet.end()) {
if (minSubstring.empty() || sub < minSubstring) {
minSubstring = sub;
}
}
}
}
result[i] = minSubstring;
}
return result;
}
int main() {
std::vector<std::string> arr = {"cab", "ad", "bad", "c"};
std::vector<std::string> result = shortestUncommonSubstring(arr);
for (const std::string& res : result) {
std::cout << '"' << res << '"' << std::endl;
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> ShortestUncommonSubstring(string[] arr) {
List<string> result = new List<string>();
for (int index = 0; index < arr.Length; index++) {
HashSet<string> others = new HashSet<string>();
for (int otherIndex = 0; otherIndex < arr.Length; otherIndex++) {
if (index == otherIndex) continue;
for (int start = 0; start < arr[otherIndex].Length; start++) {
for (int end = start + 1; end <= arr[otherIndex].Length; end++) {
others.Add(arr[otherIndex].Substring(start, end - start));
}
}
}
string minSub = "";
for (int start = 0; start < arr[index].Length; start++) {
for (int end = start + 1; end <= arr[index].Length; end++) {
string sub = arr[index].Substring(start, end - start);
if (!others.Contains(sub)) {
if (minSub == "" || String.Compare(sub, minSub) < 0) {
minSub = sub;
}
}
}
}
result.Add(minSub);
}
return result;
}
public static void Main(string[] args) {
Solution solution = new Solution();
string[] arr = {"cab", "ad", "bad", "c"};
var result = solution.ShortestUncommonSubstring(arr);
foreach (var res in result) {
Console.WriteLine('"' + res + '"');
}
}
}This C++ implementation utilizes sets to store substrings of all other strings compared to the current string. By calculating all substrings in a non-target string, we avoid redundancy and save on re-calculating seen substrings, providing optimized performance. This satisfies uniqueness check requirements effectively.
Time Complexity: Approx O(n^2 * m^2 log m) due to hash operations (insertions/checks are approximately O(1) but dependent on number of substrings stored).
Space Complexity: O(n * m^2) for storing substrings in sets, albeit more efficient than full array checks.
Approach 3: Enumeration
Given the small data scale, we can directly enumerate all substrings of each string and then determine whether it is a substring of other strings.
Specifically, we first enumerate each string arr[i], then enumerate the length j of each substring from small to large, and then enumerate the starting position l of each substring. We can get the current substring as sub = arr[i][l:l+j]. Then we determine whether sub is a substring of other strings. If it is, we skip the current substring; otherwise, we update the answer.
The time complexity is O(n^2 times m^4), and the space complexity is O(m). Where n is the length of the string array arr, and m is the maximum length of the string. In this problem, m \le 20.
function shortestSubstrings(arr: string[]): string[] {
const n: number = arr.length;
const ans: string[] = Array(n).fill('');
for (let i = 0; i < n; ++i) {
const m: number = arr[i].length;
for (let j = 1; j <= m && ans[i] === ''; ++j) {
for (let l = 0; l <= m - j; ++l) {
const sub: string = arr[i].slice(l, l + j);
if (ans[i] === '' || sub.localeCompare(ans[i]) < 0) {
let ok: boolean = true;
for (let k = 0; k < n && ok; ++k) {
if (k !== i && arr[k].includes(sub)) {
ok = false;
}
}
if (ok) {
ans[i] = sub;
}
}
}
}
}
return ans;
}func shortestSubstrings(arr []string) []string {
ans := make([]string, len(arr))
for i, s := range arr {
m := len(s)
for j := 1; j <= m && len(ans[i]) == 0; j++ {
for l := 0; l <= m-j; l++ {
sub := s[l : l+j]
if len(ans[i]) == 0 || ans[i] > sub {
ok := true
for k, t := range arr {
if k != i && strings.Contains(t, sub) {
ok = false
break
}
}
if ok {
ans[i] = sub
}
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach with Substring Check | Time Complexity: O(n * m^3) where n is the number of strings and m is the maximal length of the strings. We generate all substrings of a string, which is O(m^2), and then for each substring check it against other strings which is another O(n*m) check. |
| Optimized Set Approach | Time Complexity: Approx O(n^2 * m^2 log m) due to hash operations (insertions/checks are approximately O(1) but dependent on number of substrings stored). |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Check | O(n * m^3) | O(1) | Useful for understanding the definition of uncommon substrings or when constraints are extremely small |
| Optimized Hash Set / Frequency Map | O(n * m^2) | O(n * m^2) | General case solution. Avoids repeated scanning of other strings using hash lookups |
Frequently asked questions
Is Shortest Uncommon Substring in an Array easy or hard?
Shortest Uncommon Substring in an Array is rated Medium difficulty. The challenge comes from efficiently checking substring uniqueness across multiple strings and avoiding repeated scans by using hashing or substring frequency maps.
Shortest Uncommon Substring in an Array Python/Java solution
Python and Java implementations typically generate substrings using nested loops and store counts in a dictionary or HashMap. A HashSet is used per string to ensure each substring is counted once. After computing frequencies, iterate over candidate substrings to select the shortest unique one.
How to solve Shortest Uncommon Substring in an Array in O(n*m^2)?
Generate all substrings for every string and insert them into a hash map that counts how many strings contain each substring. Use a set per string so duplicate substrings from the same string are counted once. Then iterate through that string's substrings ordered by increasing length and lexicographical order and pick the first substring whose global count equals one.
What is the best approach for Shortest Uncommon Substring in an Array?
The most practical solution enumerates all substrings for each string and stores their frequencies using a hash map. Each substring is counted once per string using a set to avoid duplicates. After building the frequency map, the shortest substring with frequency 1 is selected for each string. This runs in roughly O(n * m^2) time where m is the maximum string length.
Is Shortest Uncommon Substring in an Array asked at Google/Amazon/Meta?
Problems involving substring uniqueness, substring enumeration, and hash-based counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test string processing, hashing, and efficient substring generation.
What data structure is used in Shortest Uncommon Substring in an Array?
The core data structures are hash tables (or hash maps) and sets. The hash map tracks how many strings contain each substring, while a set prevents duplicate substrings from the same string from being counted multiple times. Some advanced solutions may also use tries or suffix structures.
What is the time complexity of Shortest Uncommon Substring in an Array?
The optimized solution runs in O(n * m^2) time because each string generates O(m^2) substrings and each substring is inserted or checked in a hash table in constant time. The brute force solution can reach O(n * m^3) due to repeated substring searches across other strings.