3076. Shortest Uncommon Substring in an Array LeetCode Solution
In this guide, you will get 3076. Shortest Uncommon Substring in an Array LeetCode Solution with the best time and space complexity. The solution to Shortest Uncommon Substring in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Uncommon Substring in an Array
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.
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.
Complexity Analysis
Time Complexity: O(n \cdot \Sigma |\texttt{arr[i]}|^2)
Space Complexity: O(n \cdot \Sigma |\texttt{arr[i]}|^2)
3076. Shortest Uncommon Substring in an Array LeetCode Solution in C++
class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
vector<string> ans;
unordered_map<string, int> count;
for (const string& s : arr) {
add(s, count);
}
for (const string& s : arr) {
remove(s, count);
ans.push_back(getMinSub(s, count));
add(s, count);
}
return ans;
}
private:
vector<string> getSubstrings(const string& s) {
vector<string> substrings;
for (int i = 0; i < s.length(); ++i)
for (int j = i + 1; j <= s.length(); ++j)
substrings.push_back(s.substr(i, j - i));
return substrings;
}
void add(const string& s, unordered_map<string, int>& count) {
for (const string& sub : getSubstrings(s))
++count[sub];
}
void remove(const string& s, unordered_map<string, int>& count) {
for (const string& sub : getSubstrings(s))
--count[sub];
}
string getMinSub(const string& s, const unordered_map<string, int>& count) {
string minSub;
for (const string& sub : getSubstrings(s)) {
if (count.at(sub) > 0)
continue;
if (minSub.empty() || sub.length() < minSub.length() ||
sub.length() == minSub.length() && sub < minSub)
minSub = sub;
}
return minSub;
}
}; /* code provided by PROGIEZ */
3076. Shortest Uncommon Substring in an Array LeetCode Solution in Java
class Solution {
public String[] shortestSubstrings(String[] arr) {
String[] ans = new String[arr.length];
Map<String, Integer> count = new HashMap<>();
for (int i = 0; i < arr.length; ++i)
add(arr[i], count);
for (int i = 0; i < arr.length; ++i) {
remove(arr[i], count);
ans[i] = getMinSub(arr[i], count);
add(arr[i], count);
}
return ans;
}
private List<String> getSubstrings(String s) {
List<String> substrings = new ArrayList<>();
for (int i = 0; i < s.length(); ++i)
for (int j = i + 1; j <= s.length(); ++j)
substrings.add(s.substring(i, j));
return substrings;
}
private void add(final String s, Map<String, Integer> count) {
for (final String sub : getSubstrings(s))
count.merge(sub, 1, Integer::sum);
}
private void remove(String s, Map<String, Integer> count) {
for (final String sub : getSubstrings(s))
count.merge(sub, -1, Integer::sum);
}
private String getMinSub(String s, Map<String, Integer> count) {
String minSub = "";
for (final String sub : getSubstrings(s)) {
if (count.get(sub) > 0)
continue;
if (minSub.equals("") || sub.length() < minSub.length() ||
sub.length() == minSub.length() && sub.compareTo(minSub) < 0)
minSub = sub;
}
return minSub;
}
} // code provided by PROGIEZ
3076. Shortest Uncommon Substring in an Array LeetCode Solution in Python
class Solution:
def shortestSubstrings(self, arr: list[str]) -> list[str]:
ans = []
count = collections.Counter()
def getSubstrings(s: str) -> Iterator[str]:
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
yield s[i:j]
def add(s: str) -> None:
"""Adds all substrings of s to `count`."""
for sub in getSubstrings(s):
count[sub] += 1
def remove(s: str) -> None:
"""Removes all substrings of s from `count`."""
for sub in getSubstrings(s):
count[sub] -= 1
def getMinSub(s: str) -> str:
minSub = ''
for sub in getSubstrings(s):
if count[sub] > 0:
continue
if minSub == ('' or
len(sub) < len(minSub) or
len(sub) == len(minSub) and sub < minSub):
minSub = sub
return minSub
for s in arr:
add(s)
for s in arr:
remove(s)
ans.append(getMinSub(s))
add(s)
return ans # code by PROGIEZ
