[Solved] Shortest Uncommon Substring in an Array Leetcode JAVA, Python , C++

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.

Solution

class Solution {
    public String[] shortestSubstrings(String[] arr) {
        String[] result = new String[arr.length];
        for (int i = 0; i < arr.length; i++) {
            String str = arr[i];
            String shortestSubstring = null;
            Map<String, Integer> substringCount = new HashMap<>();
            List<String> substrings = new ArrayList<>();
            for (int length = 1; length <= str.length(); length++) {
                for (int j = 0; j <= str.length() - length; j++) {
                    String substring = str.substring(j, j + length);
                    substringCount.put(substring, substringCount.getOrDefault(substring, 0) + 1);
                    substrings.add(substring);
                }
            }
            Collections.sort(substrings);
            for (String substring : substrings) {
                boolean isSubstringInOtherStrings = false;
                for (String otherStr : arr) {
                    if (!otherStr.equals(str) && otherStr.contains(substring)) {
                        isSubstringInOtherStrings = true;
                        break;
                    }
                }
                if (!isSubstringInOtherStrings && (shortestSubstring == null || substring.length() < shortestSubstring.length())) {
                    shortestSubstring = substring;
                    break;
                }
            }
            result[i] = shortestSubstring != null ? shortestSubstring : "";
        }
        return result;
    }
}

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<string> shortestSubstrings(vector<string>& arr) {
        vector<string> result(arr.size());
        for (int i = 0; i < arr.size(); i++) {
            string str = arr[i];
            string shortestSubstring;
            unordered_map<string, int> substringCount;
            vector<string> substrings;
            for (int length = 1; length <= str.length(); length++) {
                for (int j = 0; j <= str.length() - length; j++) {
                    string substring = str.substr(j, length);
                    substringCount[substring]++;
                    substrings.push_back(substring);
                }
            }
            sort(substrings.begin(), substrings.end());
            for (const string& substring : substrings) {
                bool isSubstringInOtherStrings = false;
                for (const string& otherStr : arr) {
                    if (otherStr != str && otherStr.find(substring) != string::npos) {
                        isSubstringInOtherStrings = true;
                        break;
                    }
                }
                if (!isSubstringInOtherStrings && (shortestSubstring.empty() || substring.length() < shortestSubstring.length())) {
                    shortestSubstring = substring;
                    break;
                }
            }
            result[i] = shortestSubstring.empty() ? "" : shortestSubstring;
        }
        return result;
    }
};

int main() {
    Solution solution;
    vector<string> arr = {"abcd", "bc", "bca", "bcd"};
    vector<string> result = solution.shortestSubstrings(arr);
    for (const string& str : result) {
        cout << str << " ";
    }
    cout << endl;
    return 0;
}