Minimum Window Substring: Finding the Smallest Containing Segment

The "Minimum Window Substring" problem is about finding the smallest substring within a larger string that contains all the characters of a target string.

Problem Statement

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Example

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

Solution Approach - Sliding Window Technique (javascript)

function minWindow(s, t) {
  let map = {};
  t.split("").forEach((char) => (map[char] = (map[char] || 0) + 1));

  let counter = Object.keys(map).length;
  let begin = 0,
    end = 0,
    head = 0;
  let minLength = Infinity;

  while (end < s.length) {
    let endChar = s[end];
    if (map[endChar] !== undefined) map[endChar]--;
    if (map[endChar] === 0) counter--;

    while (counter === 0) {
      let tempLength = end - begin + 1;
      if (tempLength < minLength) {
        minLength = tempLength;
        head = begin;
      }

      let startChar = s[begin];
      if (map[startChar] !== undefined) map[startChar]++;
      if (map[startChar] > 0) counter++;

      begin++;
    }

    end++;
  }

  return minLength === Infinity ? "" : s.substr(head, minLength);
}

Breaking Down the Solution

• Character Count Map: Create a map to count the occurrences of each character in t.
• Sliding Window: Move a window over s, expanding and contracting it while tracking character frequencies.
• Find Minimum Window: When all characters from t are in the current window, try to minimize the window size while maintaining all characters from t.

Solution in typescript

function minWindow(s: string, t: string): string {
  let charMap: { [key: string]: number } = {};
  t.split("").forEach((char) => {
    charMap[char] = (charMap[char] || 0) + 1;
  });

  let start = 0,
    end = 0,
    minLength = Infinity,
    head = 0;
  let required = Object.keys(charMap).length;

  while (end < s.length) {
    let endChar = s[end];
    if (charMap[endChar] !== undefined) charMap[endChar]--;
    if (charMap[endChar] === 0) required--;

    while (required === 0) {
      let tempLength = end - start + 1;
      if (tempLength < minLength) {
        minLength = tempLength;
        head = start;
      }

      let startChar = s[start];
      if (charMap[startChar] !== undefined) charMap[startChar]++;
      if (charMap[startChar] > 0) required++;

      start++;
    }

    end++;
  }

  return minLength === Infinity ? "" : s.substring(head, head + minLength);
}

In this TypeScript implementation:

• The minWindow function takes two strings s (the source string) and t (the target string).
• A map charMap is used to keep count of the required characters from t.
• The sliding window is defined by two pointers, start and end, which traverse the string s.
• When all required characters are within the current window, the window is contracted from the start to find the minimum length window that contains all characters of t.
• The minLength and head variables keep track of the size and starting position of the smallest valid window.
• The function returns the substring of s that represents the minimum window, or an empty string if no such window exists.

You can run this TypeScript code to find the smallest window in string s that contains all characters from string t.

Conclusion

The Minimum Window Substring problem is a key challenge in string manipulation, testing the ability to apply the sliding window technique effectively. It's commonly used in interview settings for its complexity and practical relevance in text processing.