Shortest Uncommon Substring in an Array

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atAirbnb

Shortest Uncommon Substring in an Array is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (count owners of every substring), runs in O(n · L³) time and O(n · L³) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check each candidate against every other string) up.

Problem

You are given an array arr of n non-empty lowercase strings. For each index i, find the shortest substring of arr[i] that does not appear as a substring of any other string in the array. If several substrings have that shortest length, take the lexicographically smallest one. If every substring of arr[i] also appears in some other string, use the empty string.

Return an array answer of length n where answer[i] is the substring chosen for arr[i].

Examples

Example 1

Input
arr = ["dog", "god", "good"]
Output
["do", "god", "oo"]
Why
Every single letter is shared. For "dog" both "do" and "og" are unique and "do" is smaller; "god" needs all three letters; "good" has the unique pair "oo".

Example 2

Input
arr = ["ab", "ab", "c"]
Output
["", "", "c"]
Why
The two equal strings share every substring with each other, so they get the empty string.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check each candidate against every other string)O(n² · L⁴)O(L)
Optimal (count owners of every substring)O(n · L³)O(n · L³)

1Brute force (check each candidate against every other string)

TimeO(n² · L⁴)Each of the n strings has O(L²) candidates, each checked against n - 1 strings with an O(L²) naive search.
SpaceO(L)Only the current candidate and the best one are kept, apart from the output.

For each string, generate its substrings by increasing length. For each candidate, scan all other strings with a substring search. The first length with any candidate that no other string contains gives the answer, and the smallest such candidate of that length is kept.

  1. For i in order, for len from 1 to arr[i].length:
  2. For every start position, take the candidate; skip it if a smaller one of this length already qualified.
  3. If no arr[j] with j != i contains the candidate, keep it as the best.
  4. Stop at the first length that produced a best candidate; otherwise the answer is "".
class Solution {
    public String[] shortestSubstrings(String[] arr) {
        int n = arr.length;
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            String best = "";
            String s = arr[i];
            for (int len = 1; len <= s.length() && best.isEmpty(); len++) {
                for (int start = 0; start + len <= s.length(); start++) {
                    String cand = s.substring(start, start + len);
                    if (!best.isEmpty() && cand.compareTo(best) >= 0) continue;
                    boolean unique = true;
                    for (int j = 0; j < n && unique; j++)
                        if (j != i && arr[j].contains(cand)) unique = false;
                    if (unique) best = cand;
                }
            }
            res[i] = best;
        }
        return res;
    }
}

2Optimal (count owners of every substring)

TimeO(n · L³)There are n · L² substrings, and hashing or comparing each one costs O(L).
SpaceO(n · L³)The count map stores up to n · L² keys of length up to L.

Make one pass that records, for every distinct substring, in how many different strings it occurs. Collect each string's substrings in a set first so that repeats inside one string are counted once. Then, for each string, a substring is unique exactly when its count is 1; pick the shortest, breaking ties by lexicographic order.

  1. For each string, put all its substrings into a set, then add 1 to count[sub] for every member of the set.
  2. For each string i, walk lengths from 1 upward and starts from left to right; track the smallest substring of the current length with count == 1.
  3. Stop at the first length that has one; if none exists, the answer is "".
class Solution {
    public String[] shortestSubstrings(String[] arr) {
        Map<String, Integer> count = new HashMap<>();
        for (String s : arr) {
            Set<String> seen = new HashSet<>();
            for (int i = 0; i < s.length(); i++)
                for (int j = i + 1; j <= s.length(); j++) seen.add(s.substring(i, j));
            for (String sub : seen) count.merge(sub, 1, Integer::sum);
        }
        String[] res = new String[arr.length];
        for (int k = 0; k < arr.length; k++) {
            String s = arr[k], best = "";
            for (int len = 1; len <= s.length() && best.isEmpty(); len++)
                for (int i = 0; i + len <= s.length(); i++) {
                    String sub = s.substring(i, i + len);
                    if (count.get(sub) == 1 && (best.isEmpty() || sub.compareTo(best) < 0)) best = sub;
                }
            res[k] = best;
        }
        return res;
    }
}

Edge cases to test

  • Duplicate strings in the array, which have no unique substring at all
  • A string that is a substring of another string
  • Several unique substrings of the shortest length, where the lexicographically smallest wins
  • A substring that occurs twice inside the same string but nowhere else still counts as unique

Hints

Hint 1

Substrings are short (at most 20 characters), so there are at most 210 per string and about 21,000 in total. Listing them all is fine.

Hint 2

For each string, try lengths from 1 upward; the first length that has any unique substring is the answer length, and among those pick the smallest.

Hint 3

Count, for every substring, how many different strings of the array contain it. A substring of arr[i] is unique exactly when that count is 1.

FAQ

What is the best time complexity for Shortest Uncommon Substring in an Array?

Optimal (count owners of every substring) runs in O(n · L³) time and O(n · L³) extra space. There are n · L² substrings, and hashing or comparing each one costs O(L).

Which pattern does Shortest Uncommon Substring in an Array use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Shortest Uncommon Substring in an Array?

Yes. Brute force (check each candidate against every other string) takes O(n² · L⁴) time and O(L) space. For each string, generate its substrings by increasing length.

Which edge cases should I test for Shortest Uncommon Substring in an Array?

Duplicate strings in the array, which have no unique substring at all; A string that is a substring of another string; Several unique substrings of the shortest length, where the lexicographically smallest wins; A substring that occurs twice inside the same string but nowhere else still counts as unique.