In this article, we will learn to resolve the Minimum Window Substring problem by using Sliding Window algorithm

## Problem

• Given two strings `s` of length m and `t` of length n

• Find a minimum substring in `s` which contains all characters in `t`

## Example

• Input: given two strings `aaaaaaaaaaaabbbbbcdd` and `abcdd`

• Expected output: `abbbbbcdd`

## Approach: Sliding Window

Iterating over `s` window by window with two index pointers `i` and `j` to find the minimum substring

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

public class WindowSliding_GivenString_FindMinSubstr {
public static String findMinSubstr(String s, String t) {
Map<Character, Integer> tChars = new HashMap<>();
for(char c : t.toCharArray()) {
tChars.compute(c, (key, value) -> value == null ? 1 : ++value);
}

Map<Character, Integer> sChars = new HashMap<>();
String windowSubstr = "";
String minSubstr = "";
int i = 0;
int j = 0;
int matched = 0;

while(i < s.length()) {
Character c;
while(j < s.length() && matched < tChars.size()) {
c = s.charAt(j++);
sChars.compute(c, (key, value) -> value == null ? 1 : ++value);
windowSubstr += c;

if (tChars.containsKey(c) && tChars.get(c).equals(sChars.get(c))) matched++;
}

if (matched == tChars.size() && (minSubstr.equals("") || windowSubstr.length() < minSubstr.length())){
minSubstr = windowSubstr;
}

c = windowSubstr.charAt(0);
sChars.compute(c, (key, value) -> --value);
if (tChars.containsKey(c) && tChars.get(c) > sChars.get(c)) matched--;
windowSubstr = windowSubstr.substring(1);
i++;
}

return minSubstr;
}

public static void main(String[] args) {
System.out.println(findMinSubstr("aaaaaaaaaaaabbbbbcdd", "abcdd"));
}
}
``````

Output

``````BANC
abbbbbcdd
``````

Complexity

• Time complexity: O(m+n)

• Space complexity: O(m+n)