Minimum Window Substring

Hard

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Constraints:

  • 1 <= s.length, t.length <= 105
  • s and t consist of English letters.

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Note: If there is no such window in S that covers all characters in T, return the empty string “”. If there is such a window, you are guaranteed that there will always be only one unique minimum window in S.

The question asks us to return the minimum window from the string S which has all the characters of the string T. Let us call a window desirable if it has all the characters from T. We can use a simple sliding window approach to solve this problem. In any sliding window-based problem we have two pointers. One right pointer whose job is to expand the current window and then we have the left pointer whose job is to contract a given window. At any point in time, only one of these pointers move and the other one remains fixed. The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now. The answer is the smallest desirable window. For e.g. S = "ABAACBAB" and T = "ABC". Then our answer window is "ACB" and shown below is one of the possible desirable windows.

Algorithm

  1. We start with two pointers, left and right initially pointing to the first element of the string S.
  2. We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of T.
  3. Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one, we keep on updating the minimum window size.
  4. If the window is not desirable anymore, we repeat step2 onwards.

The above steps are repeated until we have looked at all the windows. The smallest window is returned.

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

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        // Dictionary which keeps a count of all the unique characters in t.
        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

        // Number of unique characters in t, which need to be present in the
        // desired window.
        int required = dictT.size();

        // Left and Right pointer
        int l = 0, r = 0;

        // formed is used to keep track of how many unique characters in t
        // are present in the current window in its desired frequency.
        // e.g. if t is "AABC" then the window must have two A''s, one B and
        // one C.Thus formed would be = 3 when all these conditions are met.
        int formed = 0;

        // Dictionary which keeps a count of all the unique characters in the
        // current window.
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();

        // ans list of the form (window length, left, right)
        int[] ans = {-1, 0, 0};

        while (r < s.length()) {
            // Add one character from the right to the window
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);

            // If the frequency of the current character added equals to the
            // desired count in t then increment the formed count by 1.
            if (dictT.containsKey(c) && windowCounts.get(c).intValue()
                    == dictT.get(c).intValue()) {
                formed++;
            }

            // Try and contract the window till the point where it ceases to be 
            // ''desirable''.
            while (l <= r && formed == required) {
                c = s.charAt(l);
                // Save the smallest window until now.
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                // The character at the position pointed by the
                // `Left` pointer is no longer a part of the window.
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue()
                        < dictT.get(c).intValue()) {
                    formed--;
                }

                // Move the left pointer ahead, this would help to look for 
                // a new window.
                l++;
            }

            // Keep expanding the window once we are done contracting.
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

Complexity Analysis

  • Time Complexity: O(S+Twhere |S| and |T| represent the lengths of strings S and T. In the worst case we might end up visiting every element of string S twice, once by the left pointer and once by the right pointer. T represents the length of string T.
  • Space Complexity:  O(S+T) when the window size is equal to the entire string ST when T has all unique characters.

Categories: String

Tagged as: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s