Smallest Substring of All Characters

Description

Given an array of unique characters arr and a string str, Implement a function getShortestUniqueSubstring that finds the smallest substring of str containing all the characters in arr. Return "" (empty string) if such a substring doesn’t exist.

Come up with an asymptotically optimal solution and analyze the time and space complexities.

Example 1:

input:  arr = ['x','y','z'], str = "xyyzyzyx"

output: "zyx"

Constraints:

• [time limit] 5000ms
• [input] array.character arr
  • 1 ≤ arr.length ≤ 30
• [input] string str
  • 1 ≤ str.length ≤ 500
• [output] string

---

Solutions

Solution 1

Intuition

We scan the input string str from left to right while maintaining two indices - start and end

At each iteration, we examine a temporary substring [str.charAt(start),str.charAt(start+1),..., str.charAt(end)] and keep a copy of the shortest valid substring we’ve seen so far. Said differently, we keep incrementing end until the above substring contains every unique character in arr.

If the size of the resulting substring equals to arr.length then we return it since by definition there can’t be a shorter valid substring (otherwise, it’ll be missing 1 or more unique characters from arr).

Once we found a valid substring, we increment start as long the substring remains valid. At every increment we also check if the current valid substring is shorter than the previously kept one. If it is, we update ans to be the current substring.

We keep repeating the above steps in a loop until we either reach the end of the input string str or return the shortest valid substring, whichever comes first.

To examine the validity of str substrings we use 2 counters:

• unique (Integer) - the number of unique characters of arr that our current substring contains.
• map (Map/Hash Table) - the number of occurrences of each character of arr in our current substring.

Code

static String getShortestUniqueSubstring(char[] arr, String str) {
    HashMap<Character, Integer> map = new HashMap<>();
    for (char c : arr) {
        map.put(c, 0);
    }
    int unique = 0;
    String ans = "";
    for (int start = 0, end = 0; end < str.length(); end++) {
        char endChar = str.charAt(end);
        if (map.containsKey(endChar)) {
            if (map.get(endChar) == 0) {
                unique++;
            }
            map.put(endChar, map.get(endChar) + 1);
        }
        while (unique == arr.length) {
            int length = end - start + 1;
            if (length == arr.length) {
                return str.substring(start, end + 1);
            }
            if (ans.isEmpty() || length < ans.length()) {
                ans = str.substring(start, end + 1);
            }
            char startChar = str.charAt(start);
            if (map.containsKey(startChar)) {
                int count = map.get(startChar);
                if (count == 1) {
                    unique--;
                }
                map.put(startChar, count - 1);
            }
            start++;
        }
    }
    return ans;
}

Complexity

• Time Complexity: we’re doing a linear iteration of both str and arr of lengths N and M respectively, so the runtime complexity is linear in the size of the input, i.e. O(N+M).
• Space Complexity: we’re using a Map/Hash Table countMap with M key/values pairs plus few constant size counters, which together give us an O(M) space complexity (linear in the size of arr).

---

Solution 2

Intuition

Code

Complexity

• Time:
• Space:

---

Similar Questions

76. Minimum Window Substring