Minimum Window Substring Problem With Solution

Question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". A substring is a contiguous sequence of characters

Input: string = “this is a test string”, pattern = “tist” 
Output: “t stri” 
Explanation: “t stri” contains all the characters of pattern.within the string.

Minimum Window Substring Solution

Algorithm:

1. Preprocess ‘t’ and store it in a map where key is the required character and value is the required occurrences
2. Start iterating ‘s’ and keep moving forward till a character in the above created map is found
3. Store this as the starting point of a window and now expand this window till we find all characters needed in map.
4. Store the number of required character occurrences in the map. If a key’s value becomes 0, we have found all the occurrences of that particular character in the current window aka its fulfilled.
5. If we find occurrences of a character which has already been fulfilled, keep decrementing its value in the map so that it becomes negative removing excess characters from window.
6. Once every key in the map is fulfilled, start shrinking the window.
7. While shrinking, we move the pointer start pointer forward.
   • Check if the character pointed by start can be discarded.
   • If it can be discarded, we discard it and keep moving start forward.
   • Also we discard any characters not present as map keys as they anyway do not impact the fulfilment in the window.

8. While shrinking if we find that a character cannot be dropped without sacrificing the fulfilment, we first take note of the window size and see if it is smaller that the smallest found so far. If yes, we store it as the best solution found so far.
9. Now when we cannot shrink the window any further, just break out of the shrinking loop and resume expanding the window. Repeating the same process.

Minimum Window Substring Code:

// Minimum Window Substring

public String minWindow(String s, String t) {
    int n = s.length();
    int m = t.length();
    if (n == 0 || m == 0) {
        return "";
    }

    HashMap < Character, Integer > tMap = new HashMap < > ();
    HashMap < Character, Integer > uCount = new HashMap < > ();

// Store the String T's character in a map
    for (Character c: t.toCharArray()) {
        tMap.put(c, tMap.getOrDefault(c, 0) + 1);
    }
    int count = tMap.size();
    int[] ans = {-1,
        0,
        0
    };
    int l = 0, r = 0;
    int f = 0;

// Iterate over String S
    while (r < s.length()) {
        Character c = s.charAt(r);
        uCount.put(c, uCount.getOrDefault(c, 0) + 1);

// If a Character is found increment the count
        if (tMap.containsKey(c) && tMap.get(c).intValue() == uCount.get(c).intValue()) {
            f++;
        }

// When count matches with total characters, Shrink the window
        while (l <= r && f == count) {
            Character d = s.charAt(l);
            if (ans[0] == -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            uCount.put(d, uCount.get(d) - 1);
            if (tMap.containsKey(d) && uCount.get(d).intValue() < tMap.get(d).intValue()) {
                f--;
            }
            l++;
        }
        r++;

    }

    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);

}

Complexity

• Minimum Window Substring Time Complexity : O(|S| + |T|) where |S| and |T| represent the lengths of strings S and T.
• Minimum Window Substring Space Complexity : O(|S| + |T|).

Conclusion

In this article we discussed Minimum Window Substring With Detailed Solution. Checkout Other commonly asked questions here

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!