Minimum Window Substring In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Skylinewebz

Problem Statement: Minimum Window Substring

Given two strings s and t, find the minimum window in s which contains all the characters of t (including duplicate characters).

A window is defined as a substring of s, and the minimum window is the smallest substring that contains all characters of t in any order. If no such window exists, return an empty string.

Example

Example 1:

  • Input: s = "ADOBECODEBANC", t = "ABC"
  • Output: "BANC"Explanation: The smallest substring in s that contains all the characters in t is "BANC".

Example 2:

  • Input: s = "ADOBECODEBANC", t = "ABCA"
  • Output: "BANC"Explanation: The smallest substring in s that contains all the characters in t (including duplicate ‘A’) is "BANC".

Example 3:

  • Input: s = "A", t = "AA"
  • Output: ""Explanation: No such substring exists, so return an empty string.

Approach

The problem can be efficiently solved using the sliding window technique along with a hashmap to track the character frequencies in the current window.

Steps:

  1. Character Count for t: We need to know how many times each character appears in t. This can be stored in a hashmap (or a frequency array).
  2. Sliding Window: Use two pointers (left and right) to represent the current window in string s. Expand the window by moving the right pointer and contract it by moving the left pointer.
  3. Track Character Matches: As you expand the window, check if it contains all characters of t by comparing the counts of characters in the current window with those in t.
  4. Minimize the Window: Whenever a valid window is found (i.e., the window contains all characters of t), try to shrink it by moving the left pointer to the right. This will help find the smallest possible window.
  5. Result: Track the smallest valid window found during the process.

Algorithm

  1. Initialize two pointers left and right to the beginning of the string s.
  2. Use a hashmap need to store the character frequencies of t.
  3. Use another hashmap have to store the character frequencies in the current window.
  4. Expand the window by moving right pointer and update the have map.
  5. If the window contains all the characters of t, update the result if this is the smallest valid window.
  6. Contract the window by moving the left pointer and continue until no smaller valid window can be found.
  7. If no valid window is found, return an empty string.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of string s. The left and right pointers will each traverse the string once, and the operations of updating the hashmap are constant time on average.
  • Space Complexity: O(m), where m is the number of distinct characters in t. We need extra space to store the frequency maps for t and the current window.

Code Implementations

1. C++

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    unordered_map<char, int> need, have;
    for (char c : t) need[c]++;

    int left = 0, right = 0, required = need.size(), formed = 0;
    int minLen = INT_MAX, minLeft = 0;

    while (right < s.size()) {
        char c = s[right];
        have[c]++;
        
        if (have[c] == need[c]) formed++;

        while (left <= right && formed == required) {
            // Update the minimum window if necessary
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            // Contract the window from the left
            have[s[left]]--;
            if (have[s[left]] < need[s[left]]) formed--;
            left++;
        }
        right++;
    }

    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

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

2. Java

import java.util.HashMap;

public class MinWindowSubstring {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        HashMap<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        HashMap<Character, Integer> have = new HashMap<>();
        int left = 0, right = 0, required = need.size(), formed = 0;
        int minLen = Integer.MAX_VALUE, minLeft = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            have.put(c, have.getOrDefault(c, 0) + 1);

            if (have.get(c).equals(need.get(c))) {
                formed++;
            }

            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }

                have.put(s.charAt(left), have.get(s.charAt(left)) - 1);
                if (have.get(s.charAt(left)) < need.get(s.charAt(left))) {
                    formed--;
                }
                left++;
            }
            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }

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

3. Python

from collections import Counter

def minWindow(s, t):
    if not s or not t:
        return ""

    need = Counter(t)
    have = Counter()
    left, right = 0, 0
    required = len(need)
    formed = 0
    min_len = float('inf')
    min_left = 0

    while right < len(s):
        c = s[right]
        have[c] += 1
        
        if have[c] == need[c]:
            formed += 1

        while left <= right and formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left

            have[s[left]] -= 1
            if have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1
        right += 1

    return s[min_left:min_left + min_len] if min_len != float('inf') else ""

# Example usage
s = "ADOBECODEBANC"
t = "ABC"
print("Minimum Window Substring:", minWindow(s, t))

4. C#

using System;
using System.Collections.Generic;

public class MinWindowSubstring
{
    public static string MinWindow(string s, string t)
    {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";

        var need = new Dictionary<char, int>();
        foreach (var c in t)
        {
            if (!need.ContainsKey(c)) need[c] = 0;
            need[c]++;
        }

        var have = new Dictionary<char, int>();
        int left = 0, right = 0, required = need.Count, formed = 0;
        int minLen = int.MaxValue, minLeft = 0;

        while (right < s.Length)
        {
            char c = s[right];
            if (!have.ContainsKey(c)) have[c] = 0;
            have[c]++;

            if (have[c] == need[c]) formed++;

            while (left <= right && formed == required)
            {
                if (right - left + 1 < minLen)
                {
                    minLen = right - left + 1;
                    minLeft = left;
                }

                have[s[left]]--;
                if (have[s[left]] < need[s[left]]) formed--;
                left++;
            }
            right++;
        }

        return minLen == int.MaxValue ? "" : s.Substring(minLeft, minLen);
    }

    public static void Main()
    {
        string s = "ADOBECODEBANC", t = "ABC";
        Console.WriteLine("Minimum Window Substring: " + MinWindow(s, t));
    }
}

5. JavaScript

function minWindow(s, t) {
    if (!s || !t) return "";

    const need = {};
    const have = {};
    for (let char of t) {
        need[char] = (need[char] || 0) + 1;
    }

    let left = 0, right = 0;
    let required = Object.keys(need).length;
    let formed = 0;
    let minLen = Infinity, minLeft = 0;

    while (right < s.length) {
        let c = s[right];
        have[c] = (have[c] || 0) + 1;

        if (have[c] === need[c]) formed++;

        while (left <= right && formed === required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            have[s[left]]--;
            if (have[s[left]] < need[s[left]]) formed--;
            left++;
        }
        right++;
    }

    return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}

// Example usage
const s = "ADOBECODEBANC", t = "ABC";
console.log("Minimum Window Substring:", minWindow(s, t));

Conclusion

The Minimum Window Substring problem is efficiently solvable using the sliding window technique with two pointers. The algorithm iterates over the string while maintaining a count of characters and adjusting the window size dynamically. This approach ensures that we can solve the problem in linear time, O(n), where n is the length of string s.