×

Search anything:

# Minimum Window Substring

#### String Algorithms Algorithms

Get this book -> Problems on Array: For Interviews and Competitive Programming

# Problem Statement

Given two strings `A` and `B`. We need to find the smallest substring of `A` that has all the characters in `B`. If there is no such string, then the answer will be an empty string.

Example:

``````A = "abcd"
B = "bd"
``````

Output: "bcd"

Explanation:

``````Here's all the substrings of string "abcd"
"a"
"b"
"c"
"d"
"ab"
"bc"
"cd"
"abc"
"bcd"
"abcd"
``````

Here, we can clearly see that there are two substrings of A that have all the characters in string B and those are "bcd" and "abcd". The smaller one is "bcd". So, the output is "bcd".

# Approach 1

We can find all the substrings of the string `A` that have a length greater or equal to the length of string `B` (as substrings of `A` that have a length lower than the length of string `B` cannot contain all the characters of the string) and then we can check which are the substrings that contain all the characters of string `B` and output the smallest one out of all these substrings.

## Steps

Step 1: Generate all the substrings of the string `A` that have a length greater or equals to the length of the string `B` and store them in `SUBSTRINGS`.
Step 2: Make a string `ANS` and initialise it to `A`.
Step 3: Iterate through `SUBSTRINGS` from beginning to end.
Step 4: Check if all the characters of string `B` are present in the current substring.
Step 5: If all the character of string `B` is present in the current substring and the length of the current substring is smaller than the length of `ANS` update `ANS` to current substring.
Step 6 Return `ANS`.

## Implementation

``````import java.util.ArrayList;
import java.util.List;

public class MinimumWindowSubstring {

//checks if all the characters of second string is present in first string
static boolean hasAllCharacters(String a, String b) {
int[] ac = new int[26];
int[] bc = new int[26];

for (char ch: a.toCharArray())
ac[ch - 'a'] += 1;

for (char ch: b.toCharArray())
bc[ch - 'a'] += 1;

for (int i = 0;i < 26;i++) {
if (ac[i] < bc[i])
return false;
}

return true;
}

//generates all the substrings of the str and return substrings that has length greater or equals to minLen
static List<String> getAllSubstrings(String str, int minLen) {
List<String> ans = new ArrayList<>();

int n = str.length();
for (int i = 0;i < n;i++) {
StringBuilder s = new StringBuilder();
for (int j = i;j < n;j++) {
s.append(str.charAt(j));
if (s.length() >= minLen)
}
}

return ans;
}

static String getMinimumWindowString(String a, String b) {
List<String> substrings = getAllSubstrings(a, b.length());

String ans = "";
for (var str: substrings) {
if(hasAllCharacters(str, b)) {
if (ans.length() == 0)
ans = str;
else {
if (str.length() < ans.length())
ans = str;
}
}
}

return ans;
}

public static void main(String[] args) {
String a = "dbaecbbabdcaafbddcabgba";
String b = "abbcdc";
String c = "abcd";
String d = "bd";
System.out.println(getMinimumWindowString(a, b));  // output: cbbabdc
System.out.println(getMinimumWindowString(c, d));  // output: bcd
}
}
``````

## Time and Space complexity

The time complexity for finding the smallest substring that contains all the characters is the time complexity of the method getMinmumWindowString(). Which, in turn, has the time complexity of generating all the subtrings, i.e., the time complexity of the method getAllSubstrings() and then traversing the substrings and checking if characters are present in them.

The time complexity of the method getAllSubstrings() is clearly O(n2). Checking if all the characters of a string is present in the another string is the time complexity of method hasAllCharacters() which is O(n + m). Again, traversing all the substrings takes O(n2), as there are approximately n2 substrings.

As a result, the total time complexity will be O(n2) + O(n2 * (n + m)), which is approximately O(n2 * (n + m)).

Because we are storing all the substrings of string `A` that are approximately n2 in number, the space complexity will be O(n2).

# Approach 2

Can we do something better than O(n2)? Yes, we can. The idea is to use two pointers and traverse the first string only once. It means we can achieve the same in just O(n) time. Here's how we can do so:

## Steps

Here, we want to find the smallest substring of `A` that has all the characters in `B`.The following are the steps we should take to solve the problem:

• Create a string variable `ANS` that'll hold the final answer and initialise it to an empty string.
• Create a character vs integer hashmap that contains the frequency of characters in string `B`.
• Create two integer variables `CURRENTCOUTN` and `REQUIREDCOUNT` and initialize them with 0 and the length of the string `B` , respectively.
• Create another map that will hold the frequency of acquired characters from string `A`.
• Create two integer variables `I` and `J` that holds the aquire end and release end respectively.
• Loop through each character of string `A`:
• While `I` is less than the length of string `A` minus 1:
• Increment the value of `I`.
• Acquire the character at `Ith` index by putting it into the second map.
• If the frequency of `Ith` character in the second map is less or equals to the frequency of character in the first map:
• Increament the value of `CURRENTCOUNT`.
• While `J` is less than `I` and `CURRENTCOUNT` is equals to `REQUIREDCOUNT`:
• Get the substring from string `A` from index `J + 1` to `I + 1`.
• Since, this substring could be the one we are searching for, check if it's length is less than the length of previous substring i.e. of `ANS` and if it is, update the value of `ANS` to this substring.
• Now to release the character at index `J`, simply increment the value of `J` by one.
• Check if releasing the current character makes the frequency of the character lower in the second map than the frequency of the character in the first map, then decreament the value of `CURRENTCOUNT` by one.
• Return `ANS`.

## Implementation

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

public class MinimumWindowSubstring2 {
static String getMinimumWindowSubstring(String a, String b) {
String ans = "";

Map<Character, Integer> map2 = new HashMap<>();
for (var ch: b.toCharArray())
map2.put(ch, map2.getOrDefault(ch, 0) + 1);

int cc = 0;
int minLen = b.length();

Map<Character, Integer> map1 = new HashMap<>();
int i = -1;
int j = -1;

while (i < a.length() - 1) {
//acquire
while (i < a.length() - 1 && cc < minLen) {
i++;
char ch = a.charAt(i);
map1.put(ch, map1.getOrDefault(ch, 0) + 1);

if (map1.getOrDefault(ch, 0) <= map2.getOrDefault(ch, 0))
cc++;
}

while (j < i && cc == minLen) {
String s = a.substring(j + 1, i + 1);
if (ans.length() == 0)
ans = s;
else {
if (s.length() < ans.length())
ans = s;
}

j++;
char ch = a.charAt(j);
map1.put(ch, map1.getOrDefault(ch, 0) - 1);
if (map1.get(ch) <= 0)
map1.remove(ch);

if(map1.getOrDefault(ch, 0) < map2.getOrDefault(ch, 0))
cc--;
}
}

return ans;
}

public static void main(String[] args) {
System.out.println(getMinimumWindowSubstring("dbaecbbabdcaafbddcabgba", "abc"));
System.out.println(getMinimumWindowSubstring("abcd", "bd"));
}
}
``````

## Time and Space complexity

If we observe the code closely, we find that the outer while loop and the first inner while loop are both operating on variable `i`. Only the first inner loop is responsible for the increment in value of `i`. So, the first inner loop runs total of `n` times, where `n` is length of the first string. The second inner loop also runs a total of `n` times as it's value is always less than `i`. It gives us a time complexity of O(n).

As we are storing almost all the characters of the first string and the second string (in the worst case), the space complexity will be O(n + m), where `n` is number of characters in the first string and `m` is number of characters in the second string.