Java: Minimum Window Substring

Thought Process

To find the minimum window substring in 's' that contains all characters of 't', we use a sliding window approach. We maintain a frequency hash for characters in 't' and track the number of characters still needed in the current window. As we expand the window by moving the end pointer, we decrement the frequency of characters in the hash. When all required characters are included, we try to shrink the window from the start to find the smallest valid window. This ensures we efficiently find the minimum window containing all characters of 't'. 

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

        int[] thash = new int[130];
        for (int i = 0; i < t.length(); i++) {

            char ch = t.charAt(i);
            thash[ch]++;
        }
        int elementsNeedsToBeAddedInWindow = t.length();
        int start = 0;
        int end = 0;

        boolean isWindowExist = false;
        int mnLength = Integer.MAX_VALUE;
        int head = 0;
        while (end < s.length()) {

            char ch1 = s.charAt(end);
            if (thash[ch1] > 0) // Means this element exist in the t String
                elementsNeedsToBeAddedInWindow--;

            thash[ch1]--;
            while (elementsNeedsToBeAddedInWindow == 0) { // We got the window
                isWindowExist = true;
                int length = end - start + 1;
                if (length < mnLength){
                    mnLength = length;
                    head = start;
                }

                // Time to Shrink as much as possible
                // Now, ch2 won't be part of our window
                char ch2 = s.charAt(start);
                thash[ch2]++;

                if (thash[ch2] > 0) // We lost one character of t String
                    elementsNeedsToBeAddedInWindow++;

                start++;
            }
            end++;
        }
        if (isWindowExist)
            return s.substring(head,head+mnLength);
        else
            return "";
    }
}

Code Complexity

Time Complexity: O(n + m)

The algorithm iterates through 's' and 't' once, where 'n' is the length of 's' and 'm' is the length of 't'.

Space Complexity: O(1)

The algorithm uses a fixed-size frequency hash, ensuring constant space usage.

Code copied!