Problem

Given a string and a set of characters, return the shortest substring containing all the characters in the set. If there is no such substring, return null.

Examples

Example 1

1
2
3

Input: string = "figehaeci", set = {a, e, i}
Output: "aeci"
Explanation: The substring "aeci" contains all the characters {a, e, i}.

Example 2

1
2
3

Input: string = "figehaeci", set = {x, y, z}
Output: ""
Explanation: There is no substring in "figehaeci" that contains all the characters {x, y, z}.

Solution

Method 1 - Sliding Window

To solve the problem, we can use a sliding window approach which involves expanding and contracting the window to find the shortest possible substring that contains all the characters of the given set.

Here is the approach:

  1. Initialise Data Structures: Use two hash maps to store the frequency of characters in the set and the current window.
  2. Expand and Contract Window:
    • Expand the right end of the window by moving the right pointer.
    • When the window contains all characters from the set, try to make the window smaller by moving the left pointer.
    • Update the length of the shortest valid window found during the process.
  3. Return Result: If a valid window is found, return the substring; otherwise, return null.

Code

 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
51
52

public class Solution {
    public String shortestSubstringContainingSet(String s, Set<Character> set) {
        if (s == null || set == null || set.isEmpty() || s.length() < set.size()) {
            return null;
        }

        Map<Character, Integer> charCount = new HashMap<>();
        Map<Character, Integer> windowCount = new HashMap<>();

        // Initialize the character count from set
        for (char c : set) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, minLength = Integer.MAX_VALUE, start = -1, matched = 0;

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (charCount.containsKey(rightChar)) {
                windowCount.put(rightChar, windowCount.getOrDefault(rightChar, 0) + 1);
                if (windowCount.get(rightChar).intValue() == charCount.get(rightChar).intValue()) {
                    matched++;
                }
            }

            while (matched == charCount.size()) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }

                char leftChar = s.charAt(left);
                if (charCount.containsKey(leftChar)) {
                    if (windowCount.get(leftChar).intValue() == charCount.get(leftChar).intValue()) {
                        matched--;
                    }
                    windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                }
                left++;
            }
            right++;
        }

        return start == -1 ? null : s.substring(start, start + minLength);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.shortestSubstringContainingSet("figehaeci", Set.of('a', 'e', 'i'))); // Output: aeci
        System.out.println(solution.shortestSubstringContainingSet("figehaeci", Set.of('x', 'y', 'z'))); // Output: null
    }
}
 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

class Solution:
    def shortestSubstringContainingSet(self, s: str, char_set: set) -> str or None:
        if not s or not char_set or len(char_set) > len(s):
            return None

        char_count = {char: 0 for char in char_set}
        window_count = {char: 0 for char in char_set}

        for char in char_set:
            char_count[char] += 1
        
        left, right = 0, 0
        min_length = float('inf')
        start = -1
        matched = 0

        while right < len(s):
            right_char = s[right]
            if right_char in window_count:
                window_count[right_char] += 1
                if window_count[right_char] == char_count[right_char]:
                    matched += 1
            
            while matched == len(char_count):
                if right - left + 1 < min_length:
                    min_length = right - left + 1
                    start = left
                left_char = s[left]
                if left_char in window_count:
                    if window_count[left_char] == char_count[left_char]:
                        matched -= 1
                    window_count[left_char] -= 1
                left += 1

            right += 1

        return None if start == -1 else s[start:start + min_length]

# Example usage
solution = Solution()
print(solution.shortestSubstringContainingSet("figehaeci", {'a', 'e', 'i'}))  # Output: aeci
print(solution.shortestSubstringContainingSet("figehaeci", {'x', 'y', 'z'}))  # Output: None

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string. The two pointers (left and right) each traverse the string once.
  • 🧺 Space complexity: O(m) where m is the number of unique characters in the set (for storing the frequency count in hash maps).