Minimum Window Substring

                                            
class Solution {
public:
    string minWindow(string s, string t) {
        string result = "";
        if (s.empty() || t.empty()) {
            return result;
        }

        unordered_map<char, int> target;
        for (char c : t) {
            target[c]++;
        }

        int required = target.size();
        int left = 0, right = 0;
        int formed = 0;

        unordered_map<char, int> window;

        int minLen = INT_MAX;
        int minLeft = 0;

        while (right < s.length()) {
            char c = s[right];
            window[c]++;
            if (target.find(c) != target.end() && window[c] == target[c]) {
                formed++;
            }
            while (formed == required && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                char leftChar = s[left];
                window[leftChar]--;
                if (target.find(leftChar) != target.end() && window[leftChar] < target[leftChar]) {
                    formed--;
                }
                left++;
            }
            right++;
        }

        if (minLen == INT_MAX) {
            return result;
        }

        return s.substr(minLeft, minLen);
    }
};

                                            
class Solution {
    public String minWindow(String s, String t) {
        int[] targetCharFreq = new int[128];
        for(char c : t.toCharArray()) {
            targetCharFreq[c]++;
        }
        
        int left = 0;
        int right = 0;
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        int count = t.length();
        
        while(right < s.length()) {
            if(targetCharFreq[s.charAt(right++)]-- > 0) {
                count--;
            }
            
            while(count == 0) {
                if(right - left < minLen) {
                    minLen = right - left;
                    minStart = left;
                }
                
                if(targetCharFreq[s.charAt(left++)]++ == 0) {
                    count++;
                }
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

                                            
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s or not t:
            return ""
        
        char_count = {}
        for char in t:
            char_count[char] = char_count.get(char, 0) + 1
        
        left, min_left, min_len, count = 0, 0, float('inf'), len(t)
        
        for right in range(len(s)):
            if s[right] in char_count:
                char_count[s[right]] -= 1
                if char_count[s[right]] >= 0:
                    count -= 1
            
            while count == 0:
                if right - left + 1 < min_len:
                    min_left = left
                    min_len = right - left + 1
                
                if s[left] in char_count:
                    char_count[s[left]] += 1
                    if char_count[s[left]] > 0:
                        count += 1
                left += 1
        
        return "" if min_len == float('inf') else s[min_left:min_left+min_len]

                                            
public class Solution {
    public string MinWindow(string s, string t) {
        if (s == null || s.Length == 0 || t == null || t.Length == 0) {
            return "";
        }
        
        Dictionary<char, int> targetFreq = new Dictionary<char, int>();
        foreach (char c in t) {
            if (!targetFreq.ContainsKey(c)) {
                targetFreq[c] = 0;
            }
            targetFreq[c]++;
        }
        
        int required = targetFreq.Count;
        int left = 0;
        int right = 0;
        int formed = 0;
        
        Dictionary<char, int> windowFreq = new Dictionary<char, int>();
        int[] ans = {-1, 0, 0};
        
        while (right < s.Length) {
            char c = s[right];
            if (!windowFreq.ContainsKey(c)) {
                windowFreq[c] = 0;
            }
            windowFreq[c]++;
            
            if (targetFreq.ContainsKey(c) && windowFreq[c] == targetFreq[c]) {
                formed++;
            }
            
            while (left <= right && formed == required) {
                c = s[left];
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right + 1;
                }
                
                windowFreq[c]--;
                if (targetFreq.ContainsKey(c) && windowFreq[c] < targetFreq[c]) {
                    formed--;
                }
                
                left++;
            }
            
            right++;
        }
        
        return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1]);
    }
}

                                            
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    const need = {};
    const window = {};
    let left = 0;
    let right = 0;
    let valid = 0;
    let start = 0;
    let len = Infinity;

    for (let char of t) {
        need[char] = need[char] ? need[char] + 1 : 1;
    }

    while (right < s.length) {
        const curr = s[right];
        right++;

        if (need[curr]) {
            window[curr] = window[curr] ? window[curr] + 1 : 1;
            if (window[curr] === need[curr]) {
                valid++;
            }
        }

        while (valid === Object.keys(need).length) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            const removeChar = s[left];
            left++;

            if (need[removeChar]) {
                if (window[removeChar] === need[removeChar]) {
                    valid--;
                }
                window[removeChar]--;
            }
        }
    }

    return len === Infinity ? "" : s.substr(start, len);
};

                                            
function minWindow(s: string, t: string): string {
    let left = 0;
    let right = 0;
    let charCount = new Map();
    let required = t.length;
    let minLen = Infinity;
    let minStart = 0;
    
    for (let char of t) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    while (right < s.length) {
        if (charCount.has(s[right]) && charCount.get(s[right]) > 0) {
            required--;
        }
        charCount.set(s[right], (charCount.get(s[right]) || 0) - 1);
        right++;
        
        while (required === 0) {
            if (right - left < minLen) {
                minLen = right - left;
                minStart = left;
            }
            charCount.set(s[left], (charCount.get(s[left]) || 0) + 1);
            if (charCount.get(s[left]) > 0) {
                required++;
            }
            left++;
        }
    }
    
    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
};

                                            
class Solution {
    /**
     * @param String $s
     *
     * @param String $t
     *
     * @return String
     */
    function minWindow($s, $t) {
        $start = 0;
        $len = PHP_INT_MAX;
        $left = $right = 0;
        $missing = strlen($t);
        $map = [];
        $result = '';
        
        for ($i = 0; $i < strlen($t); $i++) {
            $map[$t[$i]]++;
        }
        
        while ($right < strlen($s)) {
            if (isset($map[$s[$right]]) && $map[$s[$right]] > 0 ) {
                $missing--;
            }
            
            if (isset($map[$s[$right]])) {
                $map[$s[$right]]--;
            }
            $right++;
            
            while ($missing == 0) {
                if ($right - $left < $len) {
                    $start = $left;
                    $len = $right - $left;
                }
                if (isset($map[$s[$left]])) {
                    $map[$s[$left]]++;
                }
                if (isset($map[$s[$left]]) && $map[$s[$left]] > 0) {
                    $missing++;
                }
                $left++;
            }
        }
        
        if ($len != PHP_INT_MAX) {
            $result = substr($s, $start, $len);
        }
        
        return $result;
    }
}

                                            
class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        var dictT = [Character: Int]()
        var dictS = [Character: Int]()
        var required = 0
        var l = 0
        var r = 0
        var formed = 0
        var ans = (Int.max, -1, -1)
        
        for char in t {
            dictT[char, default: 0] += 1
        }
        
        required = dictT.count
        
        while r < s.count {
            let char = s[s.index(s.startIndex, offsetBy: r)]
            dictS[char, default: 0] += 1
            if let countInDictS = dictS[char], let countInDictT = dictT[char] {
                if countInDictS == countInDictT {
                    formed += 1
                }
            }
            
            while formed == required && l <= r {
                let currentLength = r - l + 1
                if currentLength < ans.0 {
                    ans = (currentLength, l, r)
                }
                
                let leftChar = s[s.index(s.startIndex, offsetBy: l)]
                dictS[leftChar]! -= 1
                if let leftCharCount = dictS[leftChar], let countT = dictT[leftChar] {
                    if leftCharCount < countT {
                        formed -= 1
                    }
                }
                
                l += 1
            }
            
            r += 1
        }
        
        if ans.1 == -1 {
            return ""
        } else {
            let start = s.index(s.startIndex, offsetBy: ans.1)
            let end = s.index(s.startIndex, offsetBy: ans.2)
            return String(s[start...end])
        }
    }
}

                                            
class Solution {
    fun minWindow(s: String, t: String): String {
        val tMap = mutableMapOf<Char, Int>()
        t.forEach { tMap[it] = tMap.getOrDefault(it, 0) + 1 }

        var left = 0
        var minLen = Int.MAX_VALUE
        var minStart = 0
        var remainingChars = t.length

        s.forEachIndexed { index, char ->
            if (tMap.containsKey(char)) {
                if (tMap[char]!! > 0) {
                    remainingChars--
                }
                tMap[char] = tMap[char]!! - 1
            }

            while (remainingChars == 0) {
                if (index - left + 1 < minLen) {
                    minLen = index - left + 1
                    minStart = left
                }

                val leftChar = s[left]
                if (tMap.containsKey(leftChar)) {
                    if (tMap[leftChar] == 0) {
                        remainingChars++
                    }
                    tMap[leftChar] = tMap[leftChar]!! + 1
                }

                left++
            }
        }

        return if (minLen == Int.MAX_VALUE) "" else s.substring(minStart, minStart + minLen)
    }
}

                                            
func minWindow(s string, t string) string {
    if len(s) < len(t) {
        return ""
    }

    tMap := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        tMap[t[i]]++
    }

    required, formed := len(tMap), 0
    windowCounts := make(map[byte]int)
    ans := []int{-1, 0, 0}
    l, r := 0, 0

    for r < len(s) {
        char := s[r]
        windowCounts[char]++

        if count, found := tMap[char]; found && windowCounts[char] == count {
            formed++
        }

        for l <= r && formed == required {
            char = s[l]
            if ans[0] == -1 || r-l+1 < ans[0] {
                ans[0] = r - l + 1
                ans[1] = l
                ans[2] = r
            }

            windowCounts[char]--
            if count, found := tMap[char]; found && windowCounts[char] < count {
                formed--
            }

            l++
        }

        r++
    }

    if ans[0] == -1 {
        return ""
    }
    return s[ans[1] : ans[2]+1]
}

                                            
def min_window(s, t)
    left = 0
    right = 0
    window_counts = Hash.new(0)
    t_counts = Hash.new(0)
    required_chars = t.length
    min_len = Float::INFINITY
    min_start = 0

    t.each_char do |char|
        t_counts[char] += 1
    end

    while right < s.length
        char = s[right]
        window_counts[char] += 1

        if t_counts[char] > 0 && window_counts[char] <= t_counts[char]
            required_chars -= 1
        end

        while required_chars.zero?
            if right - left + 1 < min_len
                min_len = right - left + 1
                min_start = left
            end

            window_counts[s[left]] -= 1
            if t_counts[s[left]] > 0 && window_counts[s[left]] < t_counts[s[left]]
                required_chars += 1
            end

            left += 1
        end

        right += 1
    end

    min_len == Float::INFINITY ? "" : s[min_start, min_len]
end

                                            
object Solution {
    def minWindow(s: String, t: String): String = {
        val need = scala.collection.mutable.Map[Char, Int]()
        val window = scala.collection.mutable.Map[Char, Int]()

        t.foreach(char => need(char) = need.getOrElse(char, 0) + 1)

        var left = 0
        var right = 0
        var valid = 0
        var start = 0
        var len = Int.MaxValue

        while (right < s.length) {
            val c = s(right)
            right += 1
            if (need.contains(c)) {
                window(c) = window.getOrElse(c, 0) + 1
                if (window(c) == need(c)) valid += 1
            }

            while (valid == need.size) {
                if (right - left < len) {
                    start = left
                    len = right - left
                }

                val d = s(left)
                left += 1
                if (need.contains(d)) {
                    if (window(d) == need(d)) valid -= 1
                    window(d) = window(d) - 1
                }
            }
        }

        if (len == Int.MaxValue) ""
        else s.substring(start, start + len)
    }
}

                                            
use std::collections::HashMap;

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let (s_chars, t_chars) = (s.chars().collect::<Vec<char>>(), t.chars().collect::<Vec<char>>());
        let mut t_map: HashMap<char, i32> = HashMap::new();
        for &c in &t_chars {
            *t_map.entry(c).or_insert(0) += 1;
        }
        let (mut left, mut right, mut required, mut formed) = (0, 0, t_map.len(), 0);
        let mut window_counts: HashMap<char, i32> = HashMap::new();
        let mut ans: (i32, i32) = (-1, 0);
        let mut min_len = std::i32::MAX;
        
        while right < s_chars.len() {
            let char_right = s_chars[right];
            *window_counts.entry(char_right).or_insert(0) += 1;
            if let Some(&t_req) = t_map.get(&char_right) {
                if window_counts[&char_right] == t_req {
                    formed += 1;
                }
            }
            while left <= right && formed == required {
                if right as i32 - left as i32 + 1 < min_len {
                    min_len = right as i32 - left as i32 + 1;
                    ans = (left as i32, (right + 1) as i32);
                }
                let char_left = s_chars[left];
                *window_counts.get_mut(&char_left).unwrap() -= 1;
                if let Some(&t_req) = t_map.get(&char_left) {
                    if window_counts[&char_left] < t_req {
                        formed -= 1;
                    }
                }
                left += 1;
            }
            right += 1;
        }
        
        if ans.0 == -1 {
            return String::new();
        } else {
            return s_chars[ans.0 as usize..ans.1 as usize].iter().collect();
        }
    }
}

To solve this coding challenge, we need to find the minimum window substring in a given string \( s \) that includes all the characters in another string \( t \). The challenge is to ensure that our solution is efficient, ideally running in \( O(m + n) \) time, where \( m \) is the length of \( s \) and \( n \) is the length of \( t \). The problem can be approached using the "sliding window" technique along with a hash map to keep track of the character counts. Here’s a detailed explanation and methodology to solve the given problem:

Explanation

Initial Setup :

If either string \( s \) or \( t \) is empty, return an empty string as no window can satisfy the requirements.

Character Count Map :

Create a dictionary (hash map) called
char_count

to count the frequency of each character in \( t \). This map will help us check if a window has all the characters required by \( t \).

Two Pointers :

Initiate two pointers,
left

and
right

. The
right

pointer expands the window, and the
left

pointer contracts the window when we have a valid window containing all characters of \( t \).

Sliding Window :

Move the
right

pointer to expand the window until it contains all characters from \( t \).
Once all characters are included in the current window, try to shrink the window from the left to find the minimum length window. Update the result whenever a smaller valid window is found.
During window contraction, if any character is removed from the window and the window no longer contains all characters from \( t \), move the
left

pointer to re-expand the window by moving the
right

pointer again.

Update Result :

Keep track of the minimum window length found and update the starting position of this window.

Return the Result :

If no valid window is found, return an empty string. Otherwise, return the substring corresponding to the minimum window found.

Detailed Steps in Pseudocode

                                            
// Function to find the minimum window substring in s that contains all characters of t
function findMinWindowSubstring(s, t):
    // If either string s or t is empty, return empty string
    if s is empty or t is empty:
        return ""

    // Dictionary to store the character count of string t
    char_count = {}
    // Populate char_count map with characters from t
    for char in t:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1

    // Initialize variables for the sliding window technique
    left = 0
    min_left = 0
    min_len = infinity  // Min length is initially set to infinity
    count = length of t  // Number of characters we need to include in the window

    // Move the right pointer from 0 to the end of the string s
    for right in range(0, length of s):
        // If s[right] is a character we need, decrease the count in char_count
        if s[right] in char_count:
            char_count[s[right]] -= 1
            // Decrease the count only if the character count in the map is still 0 or above
            if char_count[s[right]] >= 0:
                count -= 1

        // When we have a valid window (containing all characters from t)
        while count == 0:
            // Check if the current window is smaller than the minimum found
            if right - left + 1 < min_len:
                min_left = left  // Update the starting index of the minimum window
                min_len = right - left + 1  // Update the minimum length

            // Try to contract the window from the left
            if s[left] in char_count:
                char_count[s[left]] += 1  // Need to include this character for future windows
                // If char count goes above 0, it's no longer a valid window
                if char_count[s[left]] > 0:
                    count += 1

            left += 1  // Move the left pointer to the right

    // Return the minimum window or empty string if no valid window was found
    if min_len == infinity:
        return ""
    else:
        return substring of s from min_left to min_left + min_len

In this pseudocode:

The dictionary
char_count

keeps track of the required characters and their frequencies.
Two pointers,
left

and
right

, are used to expand and contract the sliding window.
When
count

is zero, it indicates a valid window containing all characters from \( t \).
min_left

and
min_len

are used to store the start position and length of the smallest valid window found.

By following these detailed steps, the goal of finding the minimum window substring is achieved efficiently.