Shortest Uncommon Substring in an Array

medium string substring hash table

Problem

Given an array arr of n non-empty strings, build answer where answer[i] is the shortest substring of arr[i] that does not appear as a substring of any other string in arr. Break length ties by choosing the lexicographically smallest candidate. If no such substring exists, answer[i] is the empty string "".

Inputarr = ["cab", "ad", "bad", "c"]

Output["ab", "", "ba", ""]

For "cab" the length-2 uncommon substrings are "ca" and "ab"; "ab" is lexicographically smaller. "ad" and "c" have no uncommon substring at all.

arr (comma-separated strings)

def shortestSubstrings(arr):
    n = len(arr)
    # All substrings of each string, indexed by position in arr.
    subs = []
    for s in arr:
        cur = set()
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                cur.add(s[i:j])
        subs.append(cur)

    answer = []
    for i in range(n):
        # Substrings owned by every OTHER string.
        others = set()
        for k in range(n):
            if k != i:
                others |= subs[k]
        best = ""
        s = arr[i]
        # Scan by increasing length; first length with a hit wins.
        for length in range(1, len(s) + 1):
            cand = None
            for st in range(len(s) - length + 1):
                t = s[st:st + length]
                if t not in others and (cand is None or t < cand):
                    cand = t
            if cand is not None:
                best = cand
                break
        answer.append(best)
    return answer

function shortestSubstrings(arr) {
  const n = arr.length;
  // All substrings of each string, indexed by position in arr.
  const subs = arr.map(s => {
    const cur = new Set();
    for (let i = 0; i < s.length; i++)
      for (let j = i + 1; j <= s.length; j++) cur.add(s.slice(i, j));
    return cur;
  });

  const answer = [];
  for (let i = 0; i < n; i++) {
    // Substrings owned by every OTHER string.
    const others = new Set();
    for (let k = 0; k < n; k++)
      if (k !== i) for (const t of subs[k]) others.add(t);
    let best = "";
    const s = arr[i];
    // Scan by increasing length; first length with a hit wins.
    for (let len = 1; len <= s.length; len++) {
      let cand = null;
      for (let st = 0; st + len <= s.length; st++) {
        const t = s.slice(st, st + len);
        if (!others.has(t) && (cand === null || t < cand)) cand = t;
      }
      if (cand !== null) { best = cand; break; }
    }
    answer.push(best);
  }
  return answer;
}

String[] shortestSubstrings(String[] arr) {
    int n = arr.length;
    // All substrings of each string, indexed by position in arr.
    List<Set<String>> subs = new ArrayList<>();
    for (String s : arr) {
        Set<String> cur = new HashSet<>();
        for (int i = 0; i < s.length(); i++)
            for (int j = i + 1; j <= s.length(); j++) cur.add(s.substring(i, j));
        subs.add(cur);
    }

    String[] answer = new String[n];
    for (int i = 0; i < n; i++) {
        // Substrings owned by every OTHER string.
        Set<String> others = new HashSet<>();
        for (int k = 0; k < n; k++) if (k != i) others.addAll(subs.get(k));
        String best = "", s = arr[i];
        // Scan by increasing length; first length with a hit wins.
        for (int len = 1; len <= s.length(); len++) {
            String cand = null;
            for (int st = 0; st + len <= s.length(); st++) {
                String t = s.substring(st, st + len);
                if (!others.contains(t) && (cand == null || t.compareTo(cand) < 0)) cand = t;
            }
            if (cand != null) { best = cand; break; }
        }
        answer[i] = best;
    }
    return answer;
}

vector<string> shortestSubstrings(vector<string>& arr) {
    int n = arr.size();
    // All substrings of each string, indexed by position in arr.
    vector<unordered_set<string>> subs(n);
    for (int p = 0; p < n; p++) {
        const string& s = arr[p];
        for (int i = 0; i < (int)s.size(); i++)
            for (int j = i + 1; j <= (int)s.size(); j++) subs[p].insert(s.substr(i, j - i));
    }

    vector<string> answer(n);
    for (int i = 0; i < n; i++) {
        // Substrings owned by every OTHER string.
        unordered_set<string> others;
        for (int k = 0; k < n; k++) if (k != i) others.insert(subs[k].begin(), subs[k].end());
        string best = "", s = arr[i];
        // Scan by increasing length; first length with a hit wins.
        for (int len = 1; len <= (int)s.size(); len++) {
            string cand = ""; bool found = false;
            for (int st = 0; st + len <= (int)s.size(); st++) {
                string t = s.substr(st, len);
                if (!others.count(t) && (!found || t < cand)) { cand = t; found = true; }
            }
            if (found) { best = cand; break; }
        }
        answer[i] = best;
    }
    return answer;
}

Explanation

The constraints are tiny — at most 100 strings each of length 20 — so a brute-force over substrings is more than fast enough, and it maps cleanly onto a hash set (the trie tag just hints that prefix structures could store these substrings, but a set of strings is the simplest faithful model).

First we precompute, for each string, the set of all its substrings. A string of length L has L(L+1)/2 substrings, so with L ≤ 20 that is at most 210 per string.

To answer index i, we form others = the union of every other string's substring set. A substring of arr[i] is uncommon exactly when it is absent from others.

We want the shortest such substring, so we scan candidate lengths from 1 upward. At each length we look at every window of that size in arr[i]; among the ones not in others we keep the lexicographically smallest. The first length that produces any candidate gives the answer, and we stop. If no length yields one, the answer is "".

For ["cab","ad","bad","c"] and index 0 ("cab"): every single letter c, a, b appears elsewhere, so length 1 fails; at length 2, "ca" and "ab" are both absent elsewhere, and "ab" is lexicographically smaller, so answer[0] = "ab".

Time: O(n · L³ + n² · L²) Space: O(n · L²)