LeetCode Solutions Blog

Shortest Uncommon Substring in an Array

Number: 3356

Difficulty: Medium

Paid? No

Problem Description

Given an array arr of n non-empty strings, for each string find the shortest substring that does not occur as a substring in any other string in arr. If multiple such substrings exist, choose the lexicographically smallest one. If no such substring exists for a string, return an empty string for that position.

Key Insights

Generate all possible substrings for each string.
Process substrings in order of increasing length and lexicographical order.
For each candidate substring, check against all other strings for occurrence.
Use early stopping once a valid substring is found.
Although a Trie may optimize substring lookups, brute-force checking is practical given the small maximum string length (20) and array size (<=100).

Space and Time Complexity

Time Complexity: O(n * L^3) where L is the average string length (O(L^2) substrings per string and O(L) check for each substring). Space Complexity: O(n * L^2) if storing all substrings, though it can be optimized by generating substrings on the fly.

Solution

For each string in the array:

Generate all possible substrings.
Sort these substrings first by length and then lexicographically.
For each substring, check if it appears in any other string within the array.
Return the first valid substring found. If none exists, return an empty string.

This approach leverages the manageable constraint sizes with a straightforward brute-force method.

Code Solutions

# Python solution with clear variable names and comments

def shortest_uncommon_substring(arr):
    n = len(arr)
    answers = [""] * n

    # Helper function to generate all substrings of a given string, sorted by length and lexicographically.
    def generate_substrings(s):
        substrings = set()
        for start in range(len(s)):
            for end in range(start + 1, len(s) + 1):
                substrings.add(s[start:end])
        # Sort substrings by length first, then lexicographically.
        return sorted(list(substrings), key=lambda x: (len(x), x))
    
    # Check each string in the array.
    for i, string in enumerate(arr):
        candidate_found = False
        substrings = generate_substrings(string)
        # Check unordered substrings; first valid one is the answer.
        for substr in substrings:
            unique = True
            for j, other_string in enumerate(arr):
                if i == j:
                    continue
                if substr in other_string:
                    unique = False
                    break
            if unique:
                answers[i] = substr
                candidate_found = True
                break
        if not candidate_found:
            answers[i] = ""
    return answers

# Example usage
arr = ["cab", "ad", "bad", "c"]
print(shortest_uncommon_substring(arr))  # Expected output: ["ab", "", "ba", ""]