76. Minimum Window Substring (Hard)

https://leetcode.com/problems/minimum-window-substring/

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

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

Solutions

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        // used to keep the count of the unique characters in t.
        Map<Character, Integer> tCountMap = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            int count = tCountMap.getOrDefault(t.charAt(i), 0);
            tCountMap.put(t.charAt(i), count + 1);
        }

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

        // formedChar 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 formedChar would be = 3 when all these conditions are met.
        int formedChar = 0;

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

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

        // Left and Right pointer
        int lptr = 0;
        int rptr = 0;

        while (rptr < s.length()) {
            // Add one character from the right to the window
            char c = s.charAt(rptr);

            int count = windowCountMap.getOrDefault(c, 0);
            windowCountMap.put(c, count + 1);

            // If the frequency of the current character in current window equals to the
            // desired count in t, then increase the formedChar count by 1.
            // Be careful, it's not >= but ==, only add once after meets the desired count.

            if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() == tCountMap.get(c).intValue()) {
                formedChar++;
            }

            // Try to shrink the candidate window until it becomes the minimum sub set.
            // Prune the leftmost character if possible to minimize the length of candidate substring.
            while (lptr <= rptr && formedChar == reqChar) {

                // Update the smallest window if possible.
                if (ans[0] == -1 || (rptr - lptr + 1) < ans[0]) {
                    ans[0] = rptr - lptr + 1;
                    ans[1] = lptr;
                    ans[2] = rptr;
                }

                c = s.charAt(lptr);

                // Reduce the count of lptr character since it is no longer a part of the window.
                windowCountMap.put(c, windowCountMap.get(c) - 1);

                if (tCountMap.containsKey(c) && windowCountMap.get(c).intValue() < tCountMap.get(c).intValue()) {
                    formedChar--;
                }

                // Move the left pointer forward, this would help to look for a new window.
                // The new window are expected to has a more compact substring.

                // AAABC will be sorted out at first, then try to prune head chars if possible
                lptr++;
            }

            // Keep expanding the window on the rptr side once we are done shrinking.
            rptr++;
        }

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

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""