Minimum Window Substring ( C++, Java, Python )

In data structures and algorithms, strings contain a lot of problems and when it comes to string manipulation and pattern matching there is a very popular programming problem. In this article, we will understand the Minimum Window Substring problem and explore various approaches to solving it.

What is the Minimum Window Substring Problem?

In the Minimum Window Substring problem, we have two strings and we have to search for the smallest substring in the first string so that it contains all the characters of another string.

Let us understand it better with an example:

Input: s = “ILOVEFAVTUTOR”, t = “VAT”

Output: “AVT”

Explanation: The minimum window substring “AVT” includes ‘V’, ‘A’, and ‘T’ from string t.

Before learning about the optimal solution, let’s try to do it with brute force. In this approach, we will use the two hashmaps to store the frequency of characters in map1 we will store the frequency of each character present in string t. Below are the steps involved:

Firstly we will initialize two pointers i and j to 0. Now we will iterate through the string s with these pointers.
Now we will check if s[j] is present in map1 if present then w,e will add s[j] to map2 and increment j, map2 will contain characters of the current window.
We will check that if the value of j has reached the size of string ‘t’, that means there is a possibility that the current window has a valid substring. Now we will check if map 2 contains all the required elements by iterating through the map.
We will update the answer if the map2 contains all the required elements
Now we will increment our i and set j = i.
Now we will continue iterating through the string s by moving j to right.
If s[j] is not a valid character then we will move i to the right and do j = i and will repeat the step until we reach the end of the string s.

The Time complexity for this Approach is O(N * (log T + T)), where N is the length of string s, and T is the length of string t. The complexity arises from iterating through s with a sliding window, involving O(log T) map lookups and O(T) operations for each iteration

The Space complexity is O(T) where T is the length of string t because we store each string t character in a map.

Solution for Minimum Window Substring

In the Minimum Window Substring approach, we will optimally use the concept of sliding windows using the following steps:

We will declare two maps and in map1 we will store all characters of string t.
Firstly we will Initialize two pointers, i and j, at the beginning of the string s.
We will initialize two variables cur and total to track the current count of required characters and the total count of required characters.
We will check for each character if s[j] is required, add it to map 2, update cur, and check if cur equals total.
We will check if cur equals total then we will store the indices i and j as a potential answer and update the result.
We will slide the window by incrementing i until cur is not equal to the total we will check and update the result at each step.
We will continue iteration till j reaches the end.
At last, we will build the final answer substring using the stored indices.

In this approach, we have dynamically adjusted the window to reduce the need for comparing both maps at every step.

C++ Code

Here is the C++program to solve the minimum window substring:

#include<bits/stdc++.h>
using namespace std;

string minWindow(string s, string t) {
  // Check if string t is empty
  if (t.length() == 0) return "";

  // Frequency map for characters in t
  map < char, int > mpt;

  // Frequency map for characters in the current window
  map < char, int > mps;

  // Populate frequency map for characters in t
  for (int i = 0; i < t.length(); i++) {
    mpt[t[i]]++;
  }

  // Variables for tracking required characters
  int cur = 0, total = mpt.size();

  // Pointers for the sliding window
  int i = 0, j = 0;

  // Variables for storing the result
  int res = INT_MAX;
  pair < int, int > indices;

  // Sliding window iteration
  while (j < s.length()) {
    // If the current character is in t, update mps and check if it's needed
    if (mpt.find(s[j]) != mpt.end()) mps[s[j]]++;
    if (mpt.find(s[j]) != mpt.end() && mps[s[j]] == mpt[s[j]]) cur++;

    // Shrink the window
    while (cur == total) {
      // Update result if the current window is smaller
      if (j - i + 1 < res) {
        res = j - i + 1;
        indices = make_pair(i, j);
      }

      // Shrink the window from the left
      if (mps.find(s[i]) != mps.end()) {
        mps[s[i]]--;
        if (mps.find(s[i]) != mps.end() && mps[s[i]] < mpt[s[i]]) cur--;
      }
      i++;
    }
    // Expand the window
    j++;
  }

  // Check if a valid result was found
  if (res == INT_MAX) return "";

  // Build the final answer substring
  string str = "";
  for (int i = indices.first; i <= indices.second; i++) {
    str += s[i];
  }

  return str;
}

int main() {
  // Example usage
  string s = "ilovefavtutor", t = "vat";
  cout << "The minimum window is: " << minWindow(s, t);
  return 0;
}

Python Code

You can solve it with Python as well:

def min_window(s, t):
    if not t:
        return ""

    # Frequency dictionary for characters in t
    mpt = {}

    # Frequency dictionary for characters in the current window
    mps = {}

    # Populate frequency dictionary for characters in t
    for char in t:
        mpt[char] = mpt.get(char, 0) + 1

    # Variables for tracking required characters
    cur, total = 0, len(mpt)

    # Pointers for the sliding window
    i, j = 0, 0

    # Variables for storing the result
    res, indices = float('inf'), (0, 0)

    # Sliding window iteration
    while j < len(s):
        # If the current character is in t, update mps and check if it's needed
        if s[j] in mpt:
            mps[s[j]] = mps.get(s[j], 0) + 1
            if mps[s[j]] == mpt[s[j]]:
                cur += 1

        # Shrink the window
        while cur == total:
            # Update result if the current window is smaller
            if j - i + 1 < res:
                res = j - i + 1
                indices = (i, j)

            # Shrink the window from the left
            if s[i] in mps:
                mps[s[i]] -= 1
                if mps[s[i]] < mpt.get(s[i], 0):
                    cur -= 1
            i += 1

        # Expand the window
        j += 1

    # Check if a valid result was found
    if res == float('inf'):
        return ""

    # Build the final answer substring
    return s[indices[0]: indices[1] + 1]

# Example usage
s = "ilovefavtutor"
t = "vat"
print("The minimum window is:", min_window(s, t))

Java Code

Here is the Java solution for minimum window substring:

import java.util.HashMap;
import java.util.Map;

public class MinWindow {

    public static String minWindow(String s, String t) {
        // Check if string t is empty
        if (t.length() == 0) {
            return "";
        }

        // Frequency map for characters in t
        Map<Character, Integer> mpt = new HashMap<>();

        // Frequency map for characters in the current window
        Map<Character, Integer> mps = new HashMap<>();

        // Populate frequency map for characters in t
        for (int i = 0; i < t.length(); i++) {
            char charInT = t.charAt(i);
            mpt.put(charInT, mpt.getOrDefault(charInT, 0) + 1);
        }

        // Variables for tracking required characters
        int cur = 0, total = mpt.size();

        // Pointers for the sliding window
        int i = 0, j = 0;

        // Variables for storing the result
        int res = Integer.MAX_VALUE;
        int[] indices = new int[]{0, 0};

        // Sliding window iteration
        while (j < s.length()) {
            // If the current character is in t, update mps and check if it's needed
            char charInS = s.charAt(j);
            if (mpt.containsKey(charInS)) {
                mps.put(charInS, mps.getOrDefault(charInS, 0) + 1);
                if (mps.get(charInS).equals(mpt.get(charInS))) {
                    cur++;
                }
            }

            // Shrink the window
            while (cur == total) {
                // Update result if the current window is smaller
                if (j - i + 1 < res) {
                    res = j - i + 1;
                    indices[0] = i;
                    indices[1] = j;
                }

                // Shrink the window from the left
                char charToRemove = s.charAt(i);
                if (mps.containsKey(charToRemove)) {
                    mps.put(charToRemove, mps.get(charToRemove) - 1);
                    if (mps.get(charToRemove) < mpt.getOrDefault(charToRemove, 0)) {
                        cur--;
                    }
                }
                i++;
            }

            // Expand the window
            j++;
        }

        // Check if a valid result was found
        if (res == Integer.MAX_VALUE) {
            return "";
        }

        // Build the final answer substring
        return s.substring(indices[0], indices[1] + 1);
    }

    public static void main(String[] args) {
        // Example usage
        String s = "ilovefavtutor";
        String t = "vat";
        System.out.println("The minimum window is: " + minWindow(s, t));
    }
}

Output:

The minimum window is: avt

The Time Complexity to solve the Minimum Window Substring is O(N) because each character in the string is visited at most twice (once by i and once by j). The map operations and substring construction are constant time in this context. The Space complexity is O(T) where T is the length of string t because we store each string t character in a map.

Conclusion

In conclusion, we have discussed the Minimum Window Substring leetcode problem in which we have to find a substring from a string that contains all the characters of another string. Now you can implement the solution using C++, Java, and Python. Check out our blog for more leetcode solutions as well.