Smallest Substring of All Characters
Tags: java, algorithms, 100daysofcode, programming
Published: 2022-01-01 19:35:21

# 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

```java
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

```java

```

### Complexity

- Time:
- Space:

---

# Similar Questions

[76. Minimum Window Substring](https://www.notion.so/76-Minimum-Window-Substring-f22c566d64be491ba8e5e290fb5cdee0)