We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Uncommon Substring in an Array

Difficulty: Medium

Problem Description

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. If no such substring exists, answer[i] should be an empty string.

Key Insights

  • Each string in the array needs to be analyzed for substrings.
  • A substring is considered uncommon if it does not appear in any other string in the array.
  • The goal is to find the shortest uncommon substring, but if there are ties, the lexicographically smallest substring should be chosen.
  • Efficient substring checking can leverage hash sets or tries to avoid repeated work.

Space and Time Complexity

Time Complexity: O(n * m^2) where n is the number of strings and m is the average length of the strings. This accounts for generating substrings and checking their presence across the array.

Space Complexity: O(n * m) for storing the substrings in a hash set.

Solution

To solve the problem, we can use a two-step approach:

  1. Create a set to store all substrings of all strings in the array except the one currently being processed. This will allow for quick lookup to see if a substring is uncommon.
  2. For each string, generate all possible substrings and check against the set. Return the shortest uncommon substring found for each string, ensuring it is lexicographically smallest if there are multiple candidates.

Code Solutions

def shortest_uncommon_substring(arr):
    n = len(arr)
    answer = [''] * n
    substrings = set()
    
    # Collect all substrings from other strings
    for i in range(n):
        other_string = arr[i]
        for j in range(n):
            if i != j:
                for k in range(len(arr[j])):
                    for l in range(k + 1, len(arr[j]) + 1):
                        substrings.add(arr[j][k:l])
    
    # Find the shortest uncommon substring for each string
    for i in range(n):
        current_string = arr[i]
        min_substring = None
        
        for length in range(1, len(current_string) + 1):
            for start in range(len(current_string) - length + 1):
                substring = current_string[start:start + length]
                if substring not in substrings:
                    if min_substring is None or substring < min_substring:
                        min_substring = substring
            
            if min_substring is not None:
                break
        
        answer[i] = min_substring if min_substring is not None else ''
    
    return answer
← Back to All Questions