Skip to content

3076. Shortest Uncommon Substring in an Array 👍

  • Time: $O(n \cdot \Sigma |\texttt{arr[i]}|^2)$
  • Space: $O(n \cdot \Sigma |\texttt{arr[i]}|^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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