76. Minimum Window Substrings

This page provides solutions for the leetcode problem 76. Minimum Window Substrings.

Problem Explanation

The problem asks us to calculate the smallest window that contains all the elements of the substring $\text{t}$.

Solution

This problem can be solved using the Sliding Window technique. More such questions can be found here.

Java

import java.util.HashMap;

public class Solution {
  public String minWindow(String s, String t) {
    HashMap<Character, Integer> map = new HashMap<>();
    int required = 0;

    for(int i = 0; i < t.length(); i++) {
      char ch = t.charAt(i);
      required++;
      map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    int end = 0, start = 0, min = Integer.MAX_VALUE;
    String res = "";
    while(end < s.length()) {
      char ch = s.charAt(end++);

      if(map.containsKey(ch)) {
        map.put(ch, map.getOrDefault(ch, 0) - 1);
        if (map.get(ch) >= 0) required--;

        while(start < end && required == 0) {
          if(min > end - start) {
            min = end - start;
            res = s.substring(start, end);
          }
          char chs = s.charAt(start++);
          if(map.containsKey(chs)) map.put(chs, map.getOrDefault(chs, 0) + 1);
          if(map.getOrDefault(chs, 0) > 0) required++;
        }
      }
    }
    return res;
  }
}

Complexity

Let's say there are $\text{N}$ characters in string $\text{s}$ and $\text{M}$ characters in string $\text{t}$.

Time complexity

To calculate smallest window that contains all the elements of the substring $\text{t}$, solution iterates over all the elements of string $\text{s}$, so time complexity will be:

$$\text{O(N)}$$

Space complexity

Solution uses hashmap which has all elements of substring $\text{t}$, so space complexity will be:

$$\text{O(M)}$$