Introduction

In this blog post, we will explore how to solve the LeetCode problem "3076" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 array answer. 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.

Explanation

Here's the breakdown of the solution:

• Iterate and Check Substrings: For each string in the input array, generate all its substrings in increasing order of length.
• Uniqueness Test: For each generated substring, verify if it's present in any other string in the input array.

• Shortest Lexicographically Smallest: If a substring is unique, store it as a potential answer. Choose the shortest unique substring and, if multiple shortest substrings exist, pick the lexicographically smallest one.

• Runtime Complexity: O(n³ * m³), where n is the number of strings in the array and m is the maximum length of a string.

• Storage Complexity: O(n * m), mainly to store substrings.

Code

    def shortest_unique_substrings(arr):
    n = len(arr)
    answer = [""] * n

    for i in range(n):
        shortest_len = float('inf')
        shortest_substring = ""
        s = arr[i]
        len_s = len(s)

        for sub_len in range(1, len_s + 1):
            for j in range(len_s - sub_len + 1):
                sub = s[j:j + sub_len]
                unique = True
                for k in range(n):
                    if i != k and sub in arr[k]:
                        unique = False
                        break

                if unique:
                    if sub_len < shortest_len:
                        shortest_len = sub_len
                        shortest_substring = sub
                    elif sub_len == shortest_len and sub < shortest_substring:
                        shortest_substring = sub

        answer[i] = shortest_substring

    return answer