Shortest Uncommon Substring in an Array

Medium
1767.

Shortest Uncommon Substring in an Array

Shortest Uncommon Substring in an Array is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

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 <= 100
  • 1 <= arr[i].length <= 20
  • arr[i] consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} arr
 * @return {string[]}
 */
var shortestSubstrings = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= arr[i].length <= 20
  • arr[i] consists only of lowercase English letters

Hints for Shortest Uncommon Substring in an Array

  1. Hint 1

    Each string has at most 20 * 21 / 2 = 210 substrings, so you can afford to try them all.

  2. 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.

  3. 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

  1. For each index i and each length len = 1 .. arr[i].length:
  2. among the substrings of arr[i] of that length, keep the lexicographically smallest one that is not contained in any arr[j] with j != i;
  3. if one was found, that is answer[i] — move on to the next i.
  4. 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 res

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings