Step 1: Grasping the Problem

A strings text and characters is given. We need to return the smallest substring of text which contains all the characters in characters.

The problem would have been easier if it said all the characters is the string characters will be unique. Then we could just manage a set and push characters from text until we get all the characters. But as the characters might not be unique, instead of set, we will need a hashtable/counter to keep track of the frequencies of each characters we encounter in string text.

A substring is a sequential subset of the given string text. And we need to minimize this sequential subset to as small as possible. This tells us that a sliding window minimization approach is best to solve this problem.

We will try to keep the sliding window as small as possible. For this, first we need to start the window with 0 length. We will have to option other than increasing the window size until a valid substring is found. Whenever substring is found, we will keep it as a potential result and try shrinking the window for smaller substring. When we cannot shrink the window, we will start increasing it again until the right bound of the window reaches the end.

Below is a visual demonstration of the process. Here, text = "ADCBCAAB" and characters = "BCAC".

Step 2: Sliding Window Initialization

A sliding window needs four things to operate.

1. The left boundary of the window (left for this solution).
2. The right boundary of the window (right for this solution).
3. The target variable (best_text for this solution). This variable stores the target we want to get from the window. It can be of many variables or states like the starting and ending of the substring (which will be more efficient). But for simplicity, in this solution, we will take the substring directly.
4. Any intermediate variables to assert the conditions of window expanding/shrinking ability. In this problem, we need two python collections.Counter objects to keep track if we have all the characters we need.

Initially, we want the target variable to be the worst or unfeasible. So that it will be overwritten by any existent solution in the window expanding/shrinking loop. The initialization will look something like this:

1
2
3
4
5
6
7

chars_given = Counter(characters) # count characters
chars_taken = Counter()          # count remaining characters

best_text = "-" * (len(text) + 1) # bigger than text

left = 0                          # Window left
# right window pointer can be moved into for loops dummy variable

Step 3: Expand the window

The sliding window will run until we have reached the end of the string. But do we need the left variable to reach the end too? Yes, because we are going to need the smallest value. But we do not need that condition to check in the outer loop, we will take care in the shrinking loop.

So looping until right has reached end will suffice. And at each time window is shrank, we will get a character char. We will take it in our `chars

1
2

for right, char in enumerate(text):
    chars_taken[char] += 1       # Expand window

Step 4: Shrinking ability check

We can only expand the window when we have all the characters we need in our chars_taken counter. One way to check this is looping through all the elements in chars_given and check if that character in chars_taken is greater. Something like below:

1
2
3
4
5
6

have_all = True
for char in chars_given:
    if chars_given[char] >= chars_taken[char]:
        have_all = False
if have_all:
    # We have all the characters, so we can shrink

But python has a more elegant & operator with better time complexity to handle this. chars_given & chars_taken returns intersection of the two counters. We need to check if the intersection is equal to chars_given.

1
2

# While window can be shrunk (operator & is intersection)
while chars_taken & chars_given == chars_given:

Step 5: Get Minimum Substring

We will need to update best_text everytime when we change the window size. This is for the following reasons.

1. When expanding the window: It would not be necessary at all if we had guaranteed substring. But if it wasn’t guaranteed, best_text needs to be updated if there is only one string matching our criteria.
2. When shrinking the window: We are going to need the smallest substring matching the criteria, so each time the window shrinks, there is a possibility of getting a smaller substring, so we need to update to the smallest.

We will check the window size (right - left) with the length of best_text then update best_text by slicing if needed.

1
2
3

# Update best_text
if right - left < len(best_text):
    best_text = text[left:right+1]

Step 6: Shrink the Window

Shrinking the window means removing a character from left in this context. So we will remove a character from chars_taken as well. And finally update the window bound left.

1
2
3

# Try to shrink window 
chars_taken[text[left]] -= 1
left += 1

Step 7: Return Smallest Substring

After the while loops ends, the best_text is guaranteed to be the smallest possible substring. But, the problem statement does not guaranteed that there will be a valid substring in text. So we need to check whether there is a valid substring or not before returning best_text.

Before the loops, best_text had a dummy string with length longer than the given string. If it is not updated inside the sliding window, that means best_text will still have that large dummy string. So we can check if length is greater than length of text and then return accordingly.

1
2
3
4
5

# if no string found
if len(best_text) <= len(text):
    return best_text
else:
    return ""

Every sliding window problem takes O(n) time itself, where n is the length of text. Inside the loop, we are making a look-up in a counters which is implemented by hashtables and incrementing and decrementing variables. The intersection of counters however will take O(S) time where S is the minimum number of elements in best_text(the answer). It can be told that S is very much negligible compared to n. So the time complexity of the algorithm will remain O(n) and space complexity is also O(n) in the worst case. The program is given below.

 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

from collections import Counter

class Solution:
    def minWindow(self, text: str, characters: str) -> str:
        chars_given = Counter(characters) # count characters
        chars_taken = Counter()          # count taken characters

        best_text = "-" * (len(text) + 1) # bigger than text

        left = 0                          # Window left
        for right, char in enumerate(text):
            chars_taken[char] += 1       # Expand window

            # While window can be shrunk (operator & is intersection)
            while chars_taken & chars_given == chars_given:
                # Update best_text
                if right - left < len(best_text):
                    best_text = text[left:right+1]

                # Try to shrink window 
                chars_taken[text[left]] -= 1
                left += 1

        # if no string found
        if len(best_text) <= len(text):
            return best_text
        else:
            return ""

 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

class Solution {
    unordered_map<char, int> charsGiven;  // count given characters
    unordered_map<char, int> charsTaken;  // count taken characters
public:
    string minWindow(string text, string characters) {

        for(char character: characters)
            charsGiven[character]++;
        
        string bestText(text.length() + 1, (char)0);   // Initialize with invalid state

        int left = 0;
        for(int right = 0; right < text.length(); right++) {
            char character = text[right];
            charsTaken[character]++;
            // While window can be shrunk
            while(isValidWindow()) {
                // Update bestText
                if(right - left < bestText.length()) {
                    bestText = text.substr(left, right-left+1);
                }
                
                // Try to shrink window
                charsTaken[text[left]]--;
                left++;
            }
        }
        // If no string found, bestText will remain invalid
        if(bestText.length() > text.length())
            return "";
        return bestText;
    }

private:
    bool isValidWindow() {
        for(auto charCountPair: charsGiven) {
            if(charsTaken.find(charCountPair.first) == charsTaken.end())
                return false;
            if(charsTaken[charCountPair.first] < charsGiven[charCountPair.first])
                return false;
        }
        return true;
    }
};

 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

class Solution {
    Map<Character, Integer> charsGiven;
    Map<Character, Integer> charsTaken;

    public String minWindow(String text, String characters) {
        charsGiven = new HashMap<>();   // count given characters
        charsTaken = new HashMap<>();   // count taken characters

        for(char character : characters.toCharArray())
            charsGiven.put(character, charsGiven.getOrDefault(character, 0) + 1);
        
        String bestText = new String(new char[text.length()+1]); // Initialize with invalid state

        int left = 0;
        for(int right = 0; right < text.length(); right++) {
            char character = text.charAt(right);
            charsTaken.put(character, charsTaken.getOrDefault(character, 0) + 1);
            // While window can be shrunk
            while(isValidWindow()) {
                // Update bestText
                if(right - left < bestText.length())
                    bestText = text.substring(left, right+1);

                // Try to shrink window
                charsTaken.put(text.charAt(left), charsTaken.getOrDefault(text.charAt(left), 0) - 1);
                left++;
            }
        }
        // If no string found, bestText will remain invalid
        if(bestText.length() > text.length())
            return "";
        return bestText;
    }

    private boolean isValidWindow() {
        for(char character: charsGiven.keySet()) {
            if(!charsTaken.containsKey(character))
                return false;
            if(charsTaken.get(character) < charsGiven.get(character))
                return false;
        }
        return true;
    }
}