Shortest Uncommon Substring in an Array

Med

#2732Time: O(n^2 * m^3). For each of the `n` strings, we build a set of substrings from `n-1` other strings. Building this set takes `O(n * m^3)` time. Then, we check `O(m^2)` substrings of the current string against this set, which takes `O(m^3)`. The total time is `O(n * (n*m^3 + m^3)) = O(n^2 * m^3)`.Space: O(n * m^3), where `n` is the number of strings and `m` is their maximum length. The `otherSubstrings` set can store up to `O(n * m^2)` substrings, each of length up to `m`, leading to `O(n * m^3)` space in the worst case.3 companies

Data structures

Array Hash Table String Trie

Companies

Airbnb Affirm Moveworks

Prompt

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 of arr[i] that does not occur as a substring in any other string in arr. 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.length
2 <= n <= 100
1 <= arr[i].length <= 20
arr[i] consists only of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each string in the input array. For each string arr[i], it first builds a set of all substrings from all other strings in the array. Then, it generates all substrings of arr[i], ordered by length, and checks if they exist in the pre-computed set of "other" substrings. The first one it finds that is not in the set is the shortest uncommon substring. If multiple exist of the same shortest length, they are sorted to find the lexicographically smallest.

Algorithm

1. Initialize an answer array of size n.
1. For each string arr[i] from i = 0 to n-1:
- a. Create a HashSet<String> called otherSubstrings.
- b. For each other string arr[j] where j != i:
  - i. Generate all substrings of arr[j].
  - ii. Add each substring to otherSubstrings.
- c. Initialize foundAnswer = "".
- d. For len from 1 to arr[i].length():
  - i. Create a List<String> called candidates.
  - ii. For start from 0 to arr[i].length() - len:
    - 1. Get sub = arr[i].substring(start, start + len).
    - 1. If otherSubstrings does not contain sub, add sub to candidates.
  - iii. If candidates is not empty:
    - 1. Sort candidates lexicographically.
    - 1. Set foundAnswer = candidates.get(0).
    - 1. Break from the len loop.
- e. Set answer[i] = foundAnswer.
1. Return answer.

Walkthrough

The main idea is to solve the problem for each string arr[i] independently. For a given arr[i], we need to compare its substrings against the substrings of all arr[j] where j != i. To make this comparison efficient, we first gather all substrings from arr[j] (for all j != i) into a HashSet for quick lookups. This set, let's call it otherSubstrings, will contain every possible substring from the other words.

After building this set, we iterate through all possible substrings of arr[i], starting from length 1 up to arr[i].length(). For each length, we generate all substrings of arr[i] of that length. For each generated substring, we check if it's present in otherSubstrings. If it's not present, it's an "uncommon" substring. We collect all such uncommon substrings for the current length.

If we find any uncommon substrings, we don't need to check longer lengths. We sort the collected candidates lexicographically and pick the first one as the answer for arr[i]. We then move on to the next string in the input array. If we iterate through all possible lengths for arr[i] and find no uncommon substrings, the answer for it is an empty string. This entire process is repeated for every string in the input array.

1import java.util.*;2 3class Solution {4    public String[] shortestUncommonSubstringInArray(String[] arr) {5        int n = arr.length;6        String[] answer = new String[n];7 8        for (int i = 0; i < n; i++) {9            // Step 1: Build a set of substrings from all other strings10            Set<String> otherSubstrings = new HashSet<>();11            for (int j = 0; j < n; j++) {12                if (i == j) continue;13                for (int k = 0; k < arr[j].length(); k++) {14                    for (int l = k + 1; l <= arr[j].length(); l++) {15                        otherSubstrings.add(arr[j].substring(k, l));16                    }17                }18            }19 20            // Step 2: Find the shortest uncommon substring for arr[i]21            String shortestUncommon = "";22            for (int len = 1; len <= arr[i].length(); len++) {23                List<String> candidates = new ArrayList<>();24                for (int k = 0; k <= arr[i].length() - len; k++) {25                    String sub = arr[i].substring(k, k + len);26                    if (!otherSubstrings.contains(sub)) {27                        candidates.add(sub);28                    }29                }30                if (!candidates.isEmpty()) {31                    Collections.sort(candidates);32                    shortestUncommon = candidates.get(0);33                    break;34                }35            }36            answer[i] = shortestUncommon;37        }38        return answer;39    }40}

Complexity

Time

O(n^2 * m^3). For each of the `n` strings, we build a set of substrings from `n-1` other strings. Building this set takes `O(n * m^3)` time. Then, we check `O(m^2)` substrings of the current string against this set, which takes `O(m^3)`. The total time is `O(n * (n*m^3 + m^3)) = O(n^2 * m^3)`.

Space

O(n * m^3), where `n` is the number of strings and `m` is their maximum length. The `otherSubstrings` set can store up to `O(n * m^2)` substrings, each of length up to `m`, leading to `O(n * m^3)` space in the worst case.

Trade-offs

Pros

Relatively simple to understand and implement.

Cons

Highly inefficient due to re-computing the set of "other" substrings for each string in the input array.
The time and space complexity are high, making it unsuitable for larger constraints.

This approach improves upon the brute-force method by avoiding redundant computations. It first processes all strings to build a global map. This map stores every unique substring found across all strings as keys. The value for each key is a set of indices of the strings in which that substring appears. After this pre-computation step, it iterates through each string arr[i], generates its substrings by increasing length, and uses the map to quickly check if a substring is unique to arr[i].

Algorithm

1. Create a Map<String, Set<Integer>> called substringMap.
1. Populate the map:
- For i from 0 to n-1:
  - For len from 1 to arr[i].length():
    - For start from 0 to arr[i].length() - len:
      - Get sub = arr[i].substring(start, start + len).
      - substringMap.computeIfAbsent(sub, k -> new HashSet<>()).add(i);
1. Initialize an answer array of size n.
1. Find answers:
- For i from 0 to n-1:
  - Initialize foundAnswer = "".
  - For len from 1 to arr[i].length():
    - Create a List<String> called candidates.
    - For start from 0 to arr[i].length() - len:
      - Get sub = arr[i].substring(start, start + len).
      - If substringMap.get(sub).size() == 1:
        
        Add sub to candidates.
    - If candidates is not empty:
      - Sort candidates lexicographically.
      - Set foundAnswer = candidates.get(0).
      - Break from the len loop.
  - Set answer[i] = foundAnswer.
1. Return answer.

Walkthrough

The core optimization is to pre-process all substrings from all words at once. We use a HashMap<String, Set<Integer>> where the key is a substring and the value is a HashSet of indices i corresponding to the strings arr[i] that contain this substring.

Phase 1: Building the map. We iterate through each string arr[i] in the input array. For each arr[i], we generate all its substrings. For every substring sub, we add the index i to the set associated with sub in our map. If sub is not yet in the map, we create a new entry for it.

Phase 2: Finding the answers. After the map is fully populated, we iterate through each string arr[i] again. For each arr[i], we search for its shortest uncommon substring. We generate its substrings, ordered by length from 1 to arr[i].length(). For each substring sub, we look it up in our pre-computed map. If the size of the set of indices for sub is 1, and that single index is i, it means sub appears only in arr[i] and nowhere else. This is an uncommon substring.

We collect all such uncommon substrings of the current shortest length, sort them lexicographically, and take the smallest one as the answer for arr[i]. Once an answer is found for a given length, we can stop searching for longer substrings for arr[i] and proceed to the next string.

1import java.util.*;2 3class Solution {4    public String[] shortestUncommonSubstringInArray(String[] arr) {5        int n = arr.length;6        Map<String, Set<Integer>> substringMap = new HashMap<>();7 8        // Phase 1: Populate the map with all substrings and their occurrences9        for (int i = 0; i < n; i++) {10            for (int len = 1; len <= arr[i].length(); len++) {11                for (int start = 0; start <= arr[i].length() - len; start++) {12                    String sub = arr[i].substring(start, start + len);13                    substringMap.computeIfAbsent(sub, k -> new HashSet<>()).add(i);14                }15            }16        }17 18        String[] answer = new String[n];19        // Phase 2: Find the shortest uncommon substring for each string20        for (int i = 0; i < n; i++) {21            String shortestUncommon = "";22            for (int len = 1; len <= arr[i].length(); len++) {23                List<String> candidates = new ArrayList<>();24                for (int start = 0; start <= arr[i].length() - len; start++) {25                    String sub = arr[i].substring(start, start + len);26                    if (substringMap.get(sub).size() == 1) {27                        candidates.add(sub);28                    }29                }30                if (!candidates.isEmpty()) {31                    Collections.sort(candidates);32                    shortestUncommon = candidates.get(0);33                    break;34                }35            }36            answer[i] = shortestUncommon;37        }38        return answer;39    }40}

Complexity

Time

O(n * m^3). Populating the map takes `O(n * m^3)` because we iterate through `n` strings, each having `O(m^2)` substrings of average length `O(m)`. Finding the answers also takes `O(n * m^3)`. The total time is dominated by these two phases.

Space

O(n * m^3). The map can store up to `O(n * m^2)` unique substrings. In the worst case, each substring has length `O(m)`, leading to `O(n * m^3)` space for the keys.

Trade-offs

Pros

More efficient than the first approach by avoiding re-computation.
The logic is separated into a clean pre-computation phase and a solving phase.

Cons

The space complexity can be high if there are many long, unique substrings.

This is the most optimized approach, particularly in terms of space. It uses a Trie (prefix tree) to store all substrings from all words. Each node in the Trie stores information about which original strings contain the prefix represented by that node. By traversing the Trie, we can efficiently count the occurrences of any substring. This avoids the overhead of storing and hashing long strings as required by the HashMap approach.

Algorithm

1. Define a TrieNode class with TrieNode[] children and Set<Integer> indices.
1. Create a root TrieNode.
1. Populate the Trie:
- For i from 0 to n-1:
  - For start from 0 to arr[i].length() - 1:
    - Insert the suffix arr[i].substring(start) into the Trie.
    - During insertion, for each node along the path, add i to its indices set.
1. Initialize an answer array of size n.
1. Find answers:
- For i from 0 to n-1:
  - Find the shortest, lexicographically smallest uncommon substring for arr[i] by generating its substrings and querying the Trie.
  - For len from 1 to arr[i].length():
    - Find all uncommon substrings of length len.
    - If any are found, sort them, take the first, and break.
1. Return answer.

Walkthrough

We define a Trie data structure where each node contains an array of children (for each letter 'a' through 'z') and a Set<Integer> to store the indices of the strings that contain the substring represented by the path from the root to this node.

Phase 1: Building the Trie. We iterate through each string arr[i]. For each string, we generate all its suffixes (e.g., for "cab", the suffixes are "cab", "ab", "b"). We insert each of these suffixes into the Trie. During insertion, for every node we traverse (or create), we add the current string's index i to the node's index set. This way, after processing all strings, any path from the root to a node p represents a substring, and p.indices tells us exactly in which original strings this substring appears.

Phase 2: Finding the answers. After the Trie is built, we iterate through arr[i] one last time. For each arr[i], we generate its substrings, ordered by length and then lexicographically. For each substring sub, we traverse the Trie to find its corresponding node. We then check the size of the indices set at that node. If the size is 1, it means the substring is unique to one string (which must be arr[i], since sub is its substring). This is an uncommon substring.

As before, we find the shortest, lexicographically smallest such substring for each arr[i].

1import java.util.*;2 3class Solution {4    class TrieNode {5        TrieNode[] children = new TrieNode[26];6        Set<Integer> indices = new HashSet<>();7    }8 9    public String[] shortestUncommonSubstringInArray(String[] arr) {10        int n = arr.length;11        TrieNode root = new TrieNode();12 13        // Phase 1: Build the Trie with all substrings14        for (int i = 0; i < n; i++) {15            String s = arr[i];16            for (int j = 0; j < s.length(); j++) {17                TrieNode curr = root;18                for (int k = j; k < s.length(); k++) {19                    int charIndex = s.charAt(k) - 'a';20                    if (curr.children[charIndex] == null) {21                        curr.children[charIndex] = new TrieNode();22                    }23                    curr = curr.children[charIndex];24                    curr.indices.add(i);25                }26            }27        }28 29        String[] answer = new String[n];30        // Phase 2: Find the shortest uncommon substring for each string31        for (int i = 0; i < n; i++) {32            String s = arr[i];33            String shortestUncommon = "";34            for (int len = 1; len <= s.length(); len++) {35                List<String> candidates = new ArrayList<>();36                for (int j = 0; j <= s.length() - len; j++) {37                    String sub = s.substring(j, j + len);38                    TrieNode curr = root;39                    for (char ch : sub.toCharArray()) {40                        int charIndex = ch - 'a';41                        curr = curr.children[charIndex];42                    }43                    if (curr.indices.size() == 1) {44                        candidates.add(sub);45                    }46                }47                if (!candidates.isEmpty()) {48                    Collections.sort(candidates);49                    shortestUncommon = candidates.get(0);50                    break;51                }52            }53            answer[i] = shortestUncommon;54        }55        return answer;56    }57}

Complexity

Time

O(n * m^3). Building the Trie takes `O(n * m^2)`. Querying for all substrings for all words takes `O(n * m^3)`. The total time is dominated by the query phase.

Space

O(n * m^2). The number of nodes in the Trie is bounded by the total length of all unique substrings, which is `O(n * m^2)`. Each node has a constant-size pointer array and a set. The total size of all sets across all nodes is also bounded by `O(n * m^2)`.

Trade-offs

Pros

Best space complexity among the presented approaches.
Potentially faster in practice than the HashMap approach due to avoiding string hashing costs for long strings.

Cons

More complex to implement than the HashMap approach.

Solutions

Solution

1class Solution { public String [] shortestSubstrings ( String [] arr ) { int n = arr . length ; String [] ans = new String [ n ]; Arrays . fill ( ans , "" ); for ( int i = 0 ; i < n ; ++ i ) { int m = arr [ i ]. length (); for ( int j = 1 ; j <= m && ans [ i ]. isEmpty (); ++ j ) { for ( int l = 0 ; l <= m - j ; ++ l ) { String sub = arr [ i ]. substring ( l , l + j ); if ( ans [ i ]. isEmpty () || sub . compareTo ( ans [ i ]) < 0 ) { boolean ok = true ; for ( int k = 0 ; k < n && ok ; ++ k ) { if ( k != i && arr [ k ]. contains ( sub )) { ok = false ; } } if ( ok ) { ans [ i ] = sub ; } } } } } return ans ; } }

1class Solution { public: vector < string > shortestSubstrings ( vector < string >& arr ) { int n = arr . size (); vector < string > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { int m = arr [ i ]. size (); for ( int j = 1 ; j <= m && ans [ i ]. empty (); ++ j ) { for ( int l = 0 ; l <= m - j ; ++ l ) { string sub = arr [ i ]. substr ( l , j ); if ( ans [ i ]. empty () || sub < ans [ i ]) { bool ok = true ; for ( int k = 0 ; k < n && ok ; ++ k ) { if ( k != i && arr [ k ]. find ( sub ) != string :: npos ) { ok = false ; } } if ( ok ) { ans [ i ] = sub ; } } } } } return ans ; } };

1class Solution : def shortestSubstrings ( self , arr : List [ str ]) -> List [ str ]: ans = [ "" ] * len ( arr ) for i , s in enumerate ( arr ): m = len ( s ) for j in range ( 1 , m + 1 ): for l in range ( m - j + 1 ): sub = s [ l : l + j ] if not ans [ i ] or ans [ i ] > sub : if all ( k == i or sub not in t for k , t in enumerate ( arr )): ans [ i ] = sub if ans [ i ]: break return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public String [] shortestSubstrings ( String [] arr ) { int n = arr . length ; String [] ans = new String [ n ]; Arrays . fill ( ans , "" ); for ( int i = 0 ; i < n ; ++ i ) { int m = arr [ i ]. length (); for ( int j = 1 ; j <= m && ans [ i ]. isEmpty (); ++ j ) { for ( int l = 0 ; l <= m - j ; ++ l ) { String sub = arr [ i ]. substring ( l , l + j ); if ( ans [ i ]. isEmpty () || sub . compareTo ( ans [ i ]) < 0 ) { boolean ok = true ; for ( int k = 0 ; k < n && ok ; ++ k ) { if ( k != i && arr [ k ]. contains ( sub )) { ok = false ; } } if ( ok ) { ans [ i ] = sub ; } } } } } return ans ; } }

1class Solution { public: vector < string > shortestSubstrings ( vector < string >& arr ) { int n = arr . size (); vector < string > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { int m = arr [ i ]. size (); for ( int j = 1 ; j <= m && ans [ i ]. empty (); ++ j ) { for ( int l = 0 ; l <= m - j ; ++ l ) { string sub = arr [ i ]. substr ( l , j ); if ( ans [ i ]. empty () || sub < ans [ i ]) { bool ok = true ; for ( int k = 0 ; k < n && ok ; ++ k ) { if ( k != i && arr [ k ]. find ( sub ) != string :: npos ) { ok = false ; } } if ( ok ) { ans [ i ] = sub ; } } } } } return ans ; } };

1class Solution : def shortestSubstrings ( self , arr : List [ str ]) -> List [ str ]: ans = [ "" ] * len ( arr ) for i , s in enumerate ( arr ): m = len ( s ) for j in range ( 1 , m + 1 ): for l in range ( m - j + 1 ): sub = s [ l : l + j ] if not ans [ i ] or ans [ i ] > sub : if all ( k == i or sub not in t for k , t in enumerate ( arr )): ans [ i ] = sub if ans [ i ]: break return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.