76. Min window substring

#include <limits.h>
#include <stdlib.h>
#include <string.h>

char *minWindow(char *s, char *t) {
    int need[128] = {0};
    int ns = strlen(s), nt = strlen(t);
    for (int i = 0; i < nt; i++)
        need[(int)t[i]]++;
    int missing = nt;

    int bestStart = 0, bestLen = INT_MAX;
    int left = 0;

    for (int right = 0; right < ns; right++) {
        if (need[(int)s[right]]-- > 0)
            missing--; // this char was still needed

        while (missing == 0) { // window is valid: try to shrink
            if (right - left + 1 < bestLen) {
                bestStart = left;
                bestLen = right - left + 1;
            }
            if (++need[(int)s[left]] > 0)
                missing++; // we just removed a needed char
            left++;
        }
    }

    int len = bestLen == INT_MAX ? 0 : bestLen;
    char *res = malloc(len + 1);
    memcpy(res, s + bestStart, len);
    res[len] = '\0';
    return res;
}

76_solution1_matches.cpp

#include <climits>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
  string minWindow(string s, string t) {
    unordered_map<char, int> tfreq;
    unordered_map<char, int> wfreq;

    int left = 0;
    int matches = 0;
    int minLen = INT_MAX;
    string substr = "";

    for (char c : t)
      tfreq[c]++;

    for (int right = 0; right < s.size(); right++) {
      char c = s[right];
      wfreq[c]++;

      if (tfreq.count(c) && wfreq[c] == tfreq[c]) {
        matches++;
      }

      if (matches == tfreq.size()) {
        while (tfreq.count(s[left]) == 0 || wfreq[s[left]] > tfreq[s[left]]) {
          wfreq[s[left]]--;
          left++;

          if (left >= right || left >= s.size() - 1)
            break;
        }
        int curLen = right - left + 1;
        if (curLen < minLen) {
          substr = s.substr(left, curLen);
          minLen = curLen;
        }
      }
    }

    return substr;
  }
};

76_solution2_need_missing.cpp

#include <array>
#include <climits>
#include <string>
using namespace std;
class Solution {
public:
  string minWindow(string s, string t) {
    array<int, 128> need{};
    for (char c : t)
      need[c]++;
    int missing = t.size();

    int bestStart = 0, bestLen = INT_MAX;
    int left = 0;

    for (int right = 0; right < s.size(); right++) {
      if (need[s[right]]-- > 0)
        missing--; // this char was still needed

      while (missing == 0) { // window is valid: try to shrink
        if (right - left + 1 < bestLen) {
          bestStart = left;
          bestLen = right - left + 1;
        }
        if (++need[s[left]] > 0)
          missing++; // we just removed a needed char
        left++;
      }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
  }
};

package main

func minWindow(s string, t string) string {
    var need [128]int
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    missing := len(t)

    bestStart, bestLen := 0, len(s)+1
    left := 0

    for right := 0; right < len(s); right++ {
        if need[s[right]] > 0 {
            missing-- // this char was still needed
        }
        need[s[right]]--

        for missing == 0 { // window is valid: try to shrink
            if right-left+1 < bestLen {
                bestStart, bestLen = left, right-left+1
            }
            need[s[left]]++
            if need[s[left]] > 0 {
                missing++ // we just removed a needed char
            }
            left++
        }
    }

    if bestLen > len(s) {
        return ""
    }
    return s[bestStart : bestStart+bestLen]
}

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray())
            need[c]++;
        int missing = t.length();

        int bestStart = 0, bestLen = Integer.MAX_VALUE;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            if (need[s.charAt(right)]-- > 0)
                missing--; // this char was still needed

            while (missing == 0) { // window is valid: try to shrink
                if (right - left + 1 < bestLen) {
                    bestStart = left;
                    bestLen = right - left + 1;
                }
                if (++need[s.charAt(left)] > 0)
                    missing++; // we just removed a needed char
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

class Solution {
  minWindow(s, t) {
    const need = new Array(128).fill(0);
    for (let i = 0; i < t.length; i++) need[t.charCodeAt(i)]++;
    let missing = t.length;

    let bestStart = 0;
    let bestLen = Infinity;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
      if (need[s.charCodeAt(right)]-- > 0) missing--; // this char was still needed

      while (missing === 0) { // window is valid: try to shrink
        if (right - left + 1 < bestLen) {
          bestStart = left;
          bestLen = right - left + 1;
        }
        if (++need[s.charCodeAt(left)] > 0) missing++; // we just removed a needed char
        left++;
      }
    }
    return bestLen === Infinity ? "" : s.substring(bestStart, bestStart + bestLen);
  }
}

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = [0] * 128
        for c in t:
            need[ord(c)] += 1
        missing = len(t)

        best_start, best_len = 0, float("inf")
        left = 0

        for right, c in enumerate(s):
            if need[ord(c)] > 0:
                missing -= 1  # this char was still needed
            need[ord(c)] -= 1

            while missing == 0:  # window is valid: try to shrink
                if right - left + 1 < best_len:
                    best_start, best_len = left, right - left + 1
                need[ord(s[left])] += 1
                if need[ord(s[left])] > 0:
                    missing += 1  # we just removed a needed char
                left += 1

        return "" if best_len == float("inf") else s[best_start : best_start + best_len]

struct Solution;

impl Solution {
    fn min_window(s: String, t: String) -> String {
        let (sb, tb) = (s.as_bytes(), t.as_bytes());
        let mut need = [0i32; 128];
        for &c in tb {
            need[c as usize] += 1;
        }
        let mut missing = tb.len();

        let (mut best_start, mut best_len) = (0, usize::MAX);
        let mut left = 0;

        for right in 0..sb.len() {
            let r = sb[right] as usize;
            if need[r] > 0 {
                missing -= 1; // this char was still needed
            }
            need[r] -= 1;

            while missing == 0 {
                // window is valid: try to shrink
                if right - left + 1 < best_len {
                    best_start = left;
                    best_len = right - left + 1;
                }
                let l = sb[left] as usize;
                need[l] += 1;
                if need[l] > 0 {
                    missing += 1; // we just removed a needed char
                }
                left += 1;
            }
        }

        if best_len == usize::MAX {
            String::new()
        } else {
            s[best_start..best_start + best_len].to_string()
        }
    }
}