This is Yizhe's Blog: SlidingWindow

Sunday, January 31, 2021

76. Minimum Window Substring

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.

My answer: sliding window. Good answer with template.

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        
        Map<Character, Integer> charCount = new HashMap<Character, Integer>();

        for (int i = 0 ; i < t.length(); i ++) {
            char c = t.charAt(i);
            int count = charCount.getOrDefault(c, 0);
            count ++;
            charCount.put(c, count);
        }
        int l = 0;
        int r = 0;
        //valid is count of valid chars found in window
        int valid = 0;
        String minWindowStr = "";
        StringBuilder sb = new StringBuilder();
        boolean rMoved = true;
        
        Map<Character, Integer> currentCharCount = new HashMap<Character, Integer>();
        while(r < s.length()) {
            
            char c = s.charAt(r);
            r ++;
            
            sb.append(c);
            int count = currentCharCount.getOrDefault(c, 0);

            if (charCount.getOrDefault(c, 0) >= (count + 1)) {
                // only when expected count not reached
                // not update if already reached expected count
                valid ++;
                if (valid == t.length()) {
                    // found substr contains all chars in t
                    if(minWindowStr.length() == 0) {
                        minWindowStr = sb.toString();
                    } else if (minWindowStr.length() > sb.length()) {
                        minWindowStr = sb.toString();
                    }
                    
                }
            }
            count ++;
            currentCharCount.put(c, count);

            while (valid == t.length()) {
                if (sb.length() < minWindowStr.length()) {
                    minWindowStr = sb.toString();
                }
                char d = s.charAt(l);
                sb.deleteCharAt(0);
                l ++;
                int dCount = currentCharCount.get(d);
                dCount --;
                currentCharCount.put(d, dCount);
                if (dCount < charCount.getOrDefault(d, 0)) {
                    // deleting one d cause we have 1 less d in sb than t
                    valid --;
                }

            }
        }
        return minWindowStr;
    }
}

Saturday, January 30, 2021

978. Longest Turbulent Subarray

Given an integer array arr, return the length of a maximum size turbulent subarray of arr.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

For i <= k < j:
- arr[k] > arr[k + 1] when k is odd, and
- arr[k] < arr[k + 1] when k is even.
Or, for i <= k < j:
- arr[k] > arr[k + 1] when k is even, and
- arr[k] < arr[k + 1] when k is odd.