Shortest Uncommon Substring in an Array

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

Examples

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.

Solution

Method 1 – Hash Map of Substring Occurrences

Intuition

For each string, generate all substrings and count their occurrences across all strings. For each string, find the shortest substring that occurs only in itself.

Approach

1. For each string, generate all substrings and map them to the set of string indices in which they appear.
2. For each string, for all its substrings, if a substring appears only in this string, track the shortest and lex smallest.
3. If no such substring exists, answer is empty string.

Code

Python

class Solution:
    def shortestSubstrings(self, arr):
        n = len(arr)
        from collections import defaultdict
        occ = defaultdict(set)
        for idx, s in enumerate(arr):
            seen = set()
            for l in range(1, len(s)+1):
                for i in range(len(s)-l+1):
                    sub = s[i:i+l]
                    if sub not in seen:
                        occ[sub].add(idx)
                        seen.add(sub)
        ans = []
        for idx, s in enumerate(arr):
            best = ''
            for l in range(1, len(s)+1):
                for i in range(len(s)-l+1):
                    sub = s[i:i+l]
                    if len(occ[sub]) == 1 and idx in occ[sub]:
                        if not best or len(sub) < len(best) or (len(sub) == len(best) and sub < best):
                            best = sub
            ans.append(best)
        return ans

Java

import java.util.*;
class Solution {
    public List<String> shortestSubstrings(String[] arr) {
        int n = arr.length;
        Map<String, Set<Integer>> occ = new HashMap<>();
        for (int idx = 0; idx < n; ++idx) {
            String s = arr[idx];
            Set<String> seen = new HashSet<>();
            for (int l = 1; l <= s.length(); ++l) {
                for (int i = 0; i + l <= s.length(); ++i) {
                    String sub = s.substring(i, i+l);
                    if (seen.add(sub)) {
                        occ.computeIfAbsent(sub, k -> new HashSet<>()).add(idx);
                    }
                }
            }
        }
        List<String> ans = new ArrayList<>();
        for (int idx = 0; idx < n; ++idx) {
            String s = arr[idx], best = "";
            for (int l = 1; l <= s.length(); ++l) {
                for (int i = 0; i + l <= s.length(); ++i) {
                    String sub = s.substring(i, i+l);
                    Set<Integer> set = occ.get(sub);
                    if (set.size() == 1 && set.contains(idx)) {
                        if (best.equals("") || sub.length() < best.length() || (sub.length() == best.length() && sub.compareTo(best) < 0)) {
                            best = sub;
                        }
                    }
                }
            }
            ans.add(best);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * L^3) — n = number of strings, L = max string length (all substrings for all strings, and each substring is checked for uniqueness).
• 🧺 Space complexity: O(n * L^2) — For storing all substrings and their occurrences.