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)  
                    ans.add(s.toString());  
            }  
        }  
  
        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(n²). 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(n²), as there are approximately n² substrings.

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

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

Approach 2

Can we do something better than O(n²)? 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++;  
            }  
  
            //collect answer and release  
            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.