Sliding Window - Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution 1 - Using sliding window technique, keep track of minimum window size where characters in 't' found in 's'

In this approach, first we are going to capture characters in t and their count into a HashMap, then usnig sliding window technique find the shortest substring in s, which has all the characters from t and their count.

Implementation steps:

First, go through characters of input string t, and store the characters and their count into a HashMap, call it tMap.
Next, create following variables:
- Create a HashMap, sMap that we will use it to store characters of input string s and their count.
- left and right that we will use for the sliding window.
- requiredCount and haveCount, initialize requiredCount with size of tMap and haveCount with 0, we will use these variables to check where we have the required count of each characters in t are found in s.
- minLength to capture minimum length sliding window found so far, initialize this with Integer.MAX_VALUE since we are trying to find minimum length, and ansIndices integer array with two value to store the indices of left and right indices where minimum length sliding window found.
Next, run a while loop until right pointer reaches end of input string s, and do the following:
- Take the current character from s, and add it to the sMap.
- Next, check if the current character is present in tMap and the count of that character is same in tMap and sMap, if they are same increment haveCount, since this character satisfies the condition of matching count in both t and current window of s.
- Next, run a while loop until requiredCount and haveCount, if we find a sliding window where characters count in t matched current window of s, then we want to capture the length of that substring, and moving the slide the next characters until the condition is break again.
Next, increment right pointer to move to next character.
Finally, check if there is any minimum value found, i.e. check if minLength is still has the initialized value (Integer.MAX_VALUE), if it is then return an empty string "", otherwise return substring using the indices from ansIndices (note to use +1 on right index, since right index exclusive).

import java.util.HashMap; public class MinimumWindowSubstring { static String minWindow(String s, String t) { //first take t characters and their count into a HashMap HashMap<Character, Integer> tMap = new HashMap<>(); for(char c: t.toCharArray()) { tMap.merge(c, 1, Integer::sum); } HashMap<Character, Integer> sMap = new HashMap<>(); int left = 0; int right =0; int requiredCount = tMap.size(); int haveCount = 0; int[] ansIndices = new int[]{0,0}; int minLength = Integer.MAX_VALUE; // setting it to a maximum value since we want to find min while(right < s.length()) { char c = s.charAt(right); int sCharCount = sMap.merge(c, 1, Integer::sum); int tCharCount =tMap.getOrDefault(c, 0); if(sCharCount == tCharCount){ haveCount++; } while(haveCount == requiredCount) { if(right-left+1 <minLength) { minLength = right-left+1; ansIndices[0] = left; ansIndices[1] = right; } char leftChar = s.charAt(left++); sCharCount = sMap.merge(leftChar, -1, Integer::sum); if(tMap.containsKey(leftChar) && sCharCount < tMap.get(leftChar)) { haveCount--; } } right++; } return minLength == Integer.MAX_VALUE ? "" : s.substring(ansIndices[0], ansIndices[1]+1); } public static void main(String[] args) { System.out.println(minWindow("ADOBECODEBANC", "ABC")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input string s.
Space complexity: O(n), since we are storing characters of input strings s and t into HashMaps.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: