Minimum Window Substring - Naukri Code 360

Introduction

The Minimum Window Substring problem is a classic coding challenge that tests your ability to find the smallest substring in a string that contains all the characters of another string. This problem is usually asked in coding interviews & is a great way to improve your problem-solving skills.

In this article, we will discuss different approaches to solve this problem, which includes the naive approach, the better approach using binary search, & the expected approach using hashing & two pointers.

[Naive Approach] By Generating all the Substrings

The naive approach to solve the Minimum Window Substring problem is to generate all possible substrings of the given string & check if each substring contains all the characters of the target string.

Let’s see how the naive approach works:

1. Generate all possible substrings of the given string using nested loops.

2. For each substring, check if it contains all the characters of the target string.

3. If a substring contains all the characters, update the minimum window substring if the current substring is smaller.

4. Return the minimum window substring.

Implementation

C++
Java
Python

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

string minWindow(string s, string t) {
    int n = s.length();
    int m = t.length();
    
    if (n < m) {
        return "";
    }
    
    string ans = "";
    int minLen = INT_MAX;
    
    // Generate all substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            string substring = s.substr(i, j - i + 1);
            
            // Check if the substring contains all characters of t
            bool containsAll = true;
            unordered_map<char, int> charCount;
            for (char c : t) {
                charCount[c]++;
            }
            for (char c : substring) {
                if (charCount[c] > 0) {
                    charCount[c]--;
                }
            }
            for (auto count : charCount) {
                if (count.second > 0) {
                    containsAll = false;
                    break;
                }
            }
            
            // Update the minimum window substring
            if (containsAll && substring.length() < minLen) {
                minLen = substring.length();
                ans = substring;
            }
        }
    }
    
    return ans;
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    
    string minWindowSubstring = minWindow(s, t);
    
    cout << "Minimum Window Substring: " << minWindowSubstring << endl;
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.HashMap;

public class MinimumWindowSubstring {
    public static String minWindow(String s, String t) {
        int n = s.length();
        int m = t.length();
        
        if (n < m) {
            return "";
        }
        
        String ans = "";
        int minLen = Integer.MAX_VALUE;
        
        // Generate all substrings
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String substring = s.substring(i, j + 1);
                
                // Check if the substring contains all characters of t
                boolean containsAll = true;
                HashMap<Character, Integer> charCount = new HashMap<>();
                for (char c : t.toCharArray()) {
                    charCount.put(c, charCount.getOrDefault(c, 0) + 1);
                }
                for (char c : substring.toCharArray()) {
                    if (charCount.containsKey(c)) {
                        charCount.put(c, charCount.get(c) - 1);
                    }
                }
                for (int count : charCount.values()) {
                    if (count > 0) {
                        containsAll = false;
                        break;
                    }
                }
                
                // Update the minimum window substring
                if (containsAll && substring.length() < minLen) {
                    minLen = substring.length();
                    ans = substring;
                }
            }
        }
        
        return ans;
    }
    
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        
        String minWindowSubstring = minWindow(s, t);
        
        System.out.println("Minimum Window Substring: " + minWindowSubstring);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def minWindow(s, t):
    n = len(s)
    m = len(t)
    
    if n < m:
        return ""
    
    ans = ""
    minLen = float('inf')
    
    # Generate all substrings
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            
            # Check if the substring contains all characters of t
            containsAll = True
            charCount = {}
            for c in t:
                charCount[c] = charCount.get(c, 0) + 1
            for c in substring:
                if c in charCount:
                    charCount[c] -= 1
            for count in charCount.values():
                if count > 0:
                    containsAll = False
                    break
            
            # Update the minimum window substring
            if containsAll and len(substring) < minLen:
                minLen = len(substring)
                ans = substring
    
    return ans

s = "ADOBECODEBANC"
t = "ABC"

minWindowSubstring = minWindow(s, t)

print("Minimum Window Substring:", minWindowSubstring)

You can also try this code with Online Python Compiler

Run Code

Output

Minimum Window Substring: BANC

The time complexity of the naive approach is O(N^3) because we generate all possible substrings, which takes O(N^2) time, & for each substring, we check if it contains all the characters of the target string, which takes O(N) time. The space complexity is O(N) to store the substrings.

Note: The naive approach works normally but still it is not efficient for large strings due to its high time complexity.

[Better Approach] By using Binary Search on Answer

Instead of generating all possible substrings, we can use binary search to find the minimum window size that contains all the characters of the target string. Here's how the binary search approach works:

1. Initialize the left and right pointers to 0 and the length of the string, respectively.

2. While the left pointer is less than or equal to the right pointer:

Calculate the middle index as (left + right) / 2.
Check if a window of size middle contains all the characters of the target string.
If a window of size middle exists, update the minimum window substring and move the right pointer to middle - 1 to check for smaller window sizes.
If a window of size middle doesn't exist, move the left pointer to middle + 1 to check for larger window sizes.

3. Return the minimum window substring.

C++
Java
Python

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

bool containsAllCharacters(string s, string t, int windowSize, int &start) {
    unordered_map<char, int> charCount;
    for (char c : t) {
        charCount[c]++;
    }
    
    int count = charCount.size();
    unordered_map<char, int> windowCount;
    
    for (int i = 0; i < windowSize; i++) {
        windowCount[s[i]]++;
        if (charCount.count(s[i]) && windowCount[s[i]] == charCount[s[i]]) {
            count--;
        }
    }
    
    if (count == 0) {
        start = 0;
        return true;
    }
    
    for (int i = windowSize; i < s.length(); i++) {
        windowCount[s[i]]++;
        if (charCount.count(s[i]) && windowCount[s[i]] == charCount[s[i]]) {
            count--;
        }
        
        windowCount[s[i - windowSize]]--;
        if (charCount.count(s[i - windowSize]) && windowCount[s[i - windowSize]] < charCount[s[i - windowSize]]) {
            count++;
        }
        
        if (count == 0) {
            start = i - windowSize + 1;
            return true;
        }
    }
    
    return false;
}

string minWindow(string s, string t) {
    int left = t.size();
    int right = s.size();
    string ans = "";
    int start = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (containsAllCharacters(s, t, mid, start)) {
            ans = s.substr(start, mid);
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return ans;
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    
    string minWindowSubstring = minWindow(s, t);
    
    cout << "Minimum Window Substring: " << minWindowSubstring << endl;
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

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

public class Main {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        
        String minWindowSubstring = minWindow(s, t);
        
        System.out.println("Minimum Window Substring: " + minWindowSubstring);
    }

    public static boolean containsAllCharacters(String s, String t, int windowSize, int[] start) {
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        int count = charCount.size();
        Map<Character, Integer> windowCount = new HashMap<>();
        
        for (int i = 0; i < windowSize; i++) {
            char c = s.charAt(i);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            if (charCount.containsKey(c) && windowCount.get(c).intValue() == charCount.get(c).intValue()) {
                count--;
            }
        }
        
        if (count == 0) {
            start[0] = 0;
            return true;
        }
        
        for (int i = windowSize; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = s.charAt(i - windowSize);
            windowCount.put(c1, windowCount.getOrDefault(c1, 0) + 1);
            if (charCount.containsKey(c1) && windowCount.get(c1).intValue() == charCount.get(c1).intValue()) {
                count--;
            }
            
            windowCount.put(c2, windowCount.get(c2) - 1);
            if (charCount.containsKey(c2) && windowCount.get(c2).intValue() < charCount.get(c2).intValue()) {
                count++;
            }
            
            if (count == 0) {
                start[0] = i - windowSize + 1;
                return true;
            }
        }
        
        return false;
    }

    public static String minWindow(String s, String t) {
        int left = t.length();
        int right = s.length();
        String ans = "";
        int[] start = {-1};
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (containsAllCharacters(s, t, mid, start)) {
                ans = s.substring(start[0], start[0] + mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return ans;
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

from collections import Counter

def contains_all_characters(s, t, window_size):
    char_count = Counter(t)
    count = len(char_count)
    
    window_count = Counter(s[:window_size])
    for char in char_count:
        if window_count[char] >= char_count[char]:
            count -= 1
    
    if count == 0:
        return True, 0
    
    for i in range(window_size, len(s)):
        left_char = s[i - window_size]
        right_char = s[i]
        
        window_count[right_char] += 1
        if right_char in char_count and window_count[right_char] == char_count[right_char]:
            count -= 1
        
        window_count[left_char] -= 1
        if left_char in char_count and window_count[left_char] < char_count[left_char]:
            count += 1
        
        if count == 0:
            return True, i - window_size + 1
    
    return False, -1

def min_window(s, t):
    left = len(t)
    right = len(s)
    ans = ""
    
    while left <= right:
        mid = (left + right) // 2
        found, start = contains_all_characters(s, t, mid)
        if found:
            ans = s[start:start + mid]
            right = mid - 1
        else:
            left = mid + 1
    
    return ans

if __name__ == "__main__":
    s = "ADOBECODEBANC"
    t = "ABC"
    
    min_window_substring = min_window(s, t)
    
    print("Minimum Window Substring:", min_window_substring)

You can also try this code with Online Python Compiler

Run Code

Output

Minimum Window Substring: BANC

The binary search approach improves the time complexity to O(N*logN) by reducing the search space logarithmically. The space complexity is O(1) since we only use a hash map to keep track of character frequencies.

Note: While the binary search approach is better than the naive approach, it still has room for improvement and thats why we have the best approach, which we will discuss next.

[Expected Approach] By using Hashing and Two pointers – O(N) Time and O(1) Space

The expected approach to solve the Minimum Window Substring problem is to use hashing & two pointers. This approach optimizes the time complexity to O(N) while maintaining a space complexity of O(1).

Let’s discuss how the this approach works in step by step manner:

1. Create a hash map to store the frequency of characters in the target string.

2. Initialize two pointers, left & right, both pointing to the start of the string.

3. Move the right pointer to expand the window until the window contains all the characters of the target string.

4. Once the window contains all the characters, move the left pointer to shrink the window until the window no longer contains all the characters.

5. Update the minimum window substring if the current window size is smaller.

6. Repeat steps 3-5 until the right pointer reaches the end of the string.

7. Return the minimum window substring.

C++
Java
Python

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> charCount;
    for (char c : t) {
        charCount[c]++;
    }
    
    int required = charCount.size();
    int formed = 0;
    unordered_map<char, int> windowCount;
    int left = 0;
    int right = 0;
    int ans[2] = {-1, 0};
    
    while (right < s.length()) {
        char c = s[right];
        windowCount[c]++;
        
        if (charCount.count(c) && windowCount[c] == charCount[c]) {
            formed++;
        }
        
        while (left <= right && formed == required) {
            c = s[left];
            
            if (ans[0] == -1 || right - left + 1 < ans[1] - ans[0] + 1) {
                ans[0] = left;
                ans[1] = right;
            }
            
            windowCount[c]--;
            if (charCount.count(c) && windowCount[c] < charCount[c]) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return (ans[0] == -1) ? "" : s.substr(ans[0], ans[1] - ans[0] + 1);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    
    string minWindowSubstring = minWindow(s, t);
    
    cout << "Minimum Window Substring: " << minWindowSubstring << endl;
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.HashMap;

public class MinimumWindowSubstring {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> charCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        int required = charCount.size();
        int formed = 0;
        HashMap<Character, Integer> windowCount = new HashMap<>();
        int left = 0;
        int right = 0;
        int[] ans = {-1, 0};
        
        while (right < s.length()) {
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            
            if (charCount.containsKey(c) && windowCount.get(c).intValue() == charCount.get(c).intValue()) {
                formed++;
            }
            
            while (left <= right && formed == required) {
                c = s.charAt(left);
                
                if (ans[0] == -1 || right - left + 1 < ans[1] - ans[0] + 1) {
                    ans[0] = left;
                    ans[1] = right;
                }
                
                windowCount.put(c, windowCount.get(c) - 1);
                if (charCount.containsKey(c) && windowCount.get(c).intValue() < charCount.get(c).intValue()) {
                    formed--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return (ans[0] == -1) ? "" : s.substring(ans[0], ans[1] + 1);
    }
    
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        
        String minWindowSubstring = minWindow(s, t);
        
        System.out.println("Minimum Window Substring: " + minWindowSubstring);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python


from collections import defaultdict

def minWindow(s, t):
    charCount = defaultdict(int)
    for c in t:
        charCount[c] += 1
    
    required = len(charCount)
    formed = 0
    windowCount = defaultdict(int)
    left = 0
    right = 0
    ans = [-1, 0]
    
    while right < len(s):
        c = s[right]
        windowCount[c] += 1
        
        if c in charCount and windowCount[c] == charCount[c]:
            formed += 1
        
        while left <= right and formed == required:
            c = s[left]
            
            if ans[0] == -1 or right - left + 1 < ans[1] - ans[0] + 1:
                ans[0] = left
                ans[1] = right
            
            windowCount[c] -= 1
            if c in charCount and windowCount[c] < charCount[c]:
                formed -= 1
            
            left += 1
        
        right += 1
    
    return "" if ans[0] == -1 else s[ans[0]:ans[1]+1]

s = "ADOBECODEBANC"
t = "ABC"

minWindowSubstring = minWindow(s, t)

print("Minimum Window Substring:", minWindowSubstring)

You can also try this code with Online Python Compiler

Run Code

Output

Minimum Window Substring: BANC

The expected approach using hashing & two pointers achieves a time complexity of O(N) since we traverse the string once with the right pointer & the left pointer moves at most N steps. The space complexity is O(1) as we use hash maps of constant size to store character frequencies.

Note: This approach provides an optimal solution to the Minimum Window Substring problem, as it balances both time & space efficiency.

Frequently Asked Questions

What is the time complexity of the expected approach using hashing & two pointers?

The expected approach using hashing & two pointers has a time complexity of O(N), where N is the length of the input string. This is because we traverse the string once with the right pointer, & the left pointer moves at most N steps.

Can the Minimum Window Substring problem be solved using a sliding window approach?

Yes, the Minimum Window Substring problem can be solved using a sliding window approach. The expected approach using hashing & two pointers is essentially a sliding window technique. We expand the window by moving the right pointer & shrink the window by moving the left pointer until we find the minimum window substring.

Is it necessary to use a hash map to solve the Minimum Window Substring problem?

Using a hash map is not strictly necessary, but it provides an efficient way to keep track of the character frequencies in the window & compare them with the target string. We can use an array or a vector to store the frequencies if the character set is fixed & small (e.g., lowercase English letters). However, a hash map allows us to handle any character set efficiently.

Conclusion

In this article, we talked about the Minimum Window Substring problem & discussed different approaches to solve it. We started with the naive approach of generating all substrings, which has a time complexity of O(N^3). Then, we optimized it using binary search, which reduces its time complexity to O(N*logN). Finally, we explained the expected approach with the help of hashing & two pointers, which achieves a time complexity of O(N) & a space complexity of O(1).

You can also check out our other blogs on Code360.