Problem Statement

Given two strings s and t. Find the smallest window substring of s that includes all characters in t (including duplicates), in the window. Return the empty string "" if no such substring exists.

Examples

Example 1:

Input : s = "ADOBECODEBANC", t = "ABC"
Output : "BANC"

Explanation : The minimum window substring of string s that contains the string t is "BANC".

Example 2:

Input : s = "a", t = "a"
Output : "a"

Explanation : The complete string is the minimum window.

Example 3:

Input: s = "aAbBDdcC", t = "Bc"
Output: "BDdc"

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The idea here is to use two for loops to find out all the substrings and while finding out, keep a track of the characters present in the current substring using a hash array. If the current substring has all the characters required then store its starting index and return the substring.

Approach:

1. First, initialize few variables: minLen to Integer.MAX_VALUE to store the minimum length of the substring found and sIndex to -1 to store the starting index of this substring. Use an array hash of size 256 (assuming ASCII characters) to count frequencies of characters in the reference string.
2. Traverse through each character in string, it will indicate the starting point of the substring, for each starting index, initialize count to 0 to track how many characters from t are found in the current substring.
3. Now, again iterate through the array using a for loop form the starting point of the substring till the end of array. Update the frequency count in hash for the character current character.
4. If this character is required, increment count. When count equals the length of the another string given this means all characters from the later string are found in the current substring.
5. Update minLen and sIndex if the length of this window (j - i + 1) is smaller than the current minimum length found. After iterating through all possible starting indices, return the substring starting at sIndex with length minLen. If sIndex remains -1, return an empty string indicating no valid substring was found.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /*Function to find the minimum length substring
    in string s that contains all characters from string t.*/
    string minWindow(string s, string t) {
        
        /* Variable to store the minimum 
        length of substring found*/
        int minLen = INT_MAX;
        
        /* Variable to store the starting index
        of the minimum length substring*/
        int sIndex = -1;
        
        // Iterate through string s
        for (int i = 0; i < s.size(); ++i) {
          
            int hash[256] = {0};
            
            //Count the frquencies of characters in t.
            for (char c : t) {
                hash[c]++;
            }
            
            int count = 0;
            
            // Iterate through current window 
            for (int j = i; j < s.size(); ++j) {
                if (hash[s[j]] > 0) {
                    count++;
                }
                hash[s[j]]--;
                
                /* If all characters from t 
                are found in current window*/
                if (count == t.size()) {
                    
                    /* Update minLen and sIndex
                    if current window is smaller*/
                    if (j - i + 1 < minLen) {
                        minLen = j - i + 1;
                        sIndex = i;
                    }
                    break; 
                }
            }
        }
        
        // Return minimum length substring from s
        return (sIndex == -1) ? "" : s.substr(sIndex, minLen);
    }
};

int main() {
    string s = "ddaaabbca";
    string t = "abc";

    // Create an instance of Solution class
    Solution sol;

    string ans = sol.minWindow(s, t);

    // Print the result
    cout << "Minimum length substring containing all characters from \"" << t << "\" is: " << ans << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N is the size of the string. The outer loop runs for N time and for each character the inner loop also runs for N times.
• Space Complexity: O(256), Hash array to store frequency of all the characters.

2️⃣ Optimal Approach

Intuition:

The idea here is to use sliding window approach, which ensures to find the required result in linear time. So, basically first store the frequencies of characters of the reference string into hash array and every time while encountering the characters of the string, decrease its frequency. After doing so if the frequecy of any character is greater than 0 it means it is prefilled and the current character is needed. If the count is equal to length of reference string then update the minumum length of the substring and store its starting index.

Approach:

1. First, initialize few variables: minLen to Integer.MAX_VALUE to store the minimum length of the substring found and sIndex to -1 to store the starting index of this substring. Use an array hash of size 256 (assuming ASCII characters) to count frequencies of characters in the reference string, l (left) and r (right), both initially set to 0, to define the current window in the string.
2. Fill the hash array with frequencies of characters from string t using a loop iterating through each character in the reference string provided.
3. Expand the window by incrementing r and include the character at r pointer in the current window. Adjust the frequency count in hash for current character. If the character is required, increment count.
4. While count equals the length of reference string, attempt to shrink the window from the left (l) by incrementing l. Adjust the frequency count in hash for character at left pointer. If removing the character at left pointer reduces the count of required characters, decrement count.
5. Continue expanding and shrinking the window until r reaches the end of string. Return the substring sIndex with length minLen. If sIndex remains -1, return an empty string indicating no valid substring was found.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the minimum length 
    substring in string s that contains
    all characters from string t. */
    string minWindow(string s, string t) {
        
        /* Variable to store the minimum 
        length of substring found */
        int minLen = INT_MAX;
        
        /* Variable to store the starting index
        of the minimum length substring */
        int sIndex = -1;
        
        /* Array to count frequencies
        of characters in string t*/
        int hash[256] = {0};
        
        // Count the frequencies of characters in t
        for (char c : t) {
            hash[c]++;
        }
            
        int count = 0;
        int l = 0, r = 0;
        
        // Iterate through current window 
        while (r < s.size()) {
            // Include the current character in the window
            if (hash[s[r]] > 0) {
                count++;
            }
            hash[s[r]]--;
                
            /* If all characters from t 
            are found in current window */
            while (count == t.size()) {
                    
                /* Update minLen and sIndex
                if current window is smaller */
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    sIndex = l;
                }
                
                // Remove leftmost character from window
                hash[s[l]]++;
                if (hash[s[l]] > 0) {
                    count--;
                }
                l++;
            }
            r++;
        }
        
        // Return minimum length substring from s
        return (sIndex == -1) ? "" : s.substr(sIndex, minLen);
    }
};

int main() {
    string s = "ddaaabbca";
    string t = "abc";

    // Create an instance of Solution class
    Solution sol;

    string ans = sol.minWindow(s, t);

    // Print the result
    cout << "Minimum length substring containing all characters from \"" << t << "\" is: " << ans << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2N + M ), where N is the size of the string s and M is the size of the string t.
• Space Complexity: O(256), Hash array to store frequency of all the characters.