Problem Overview

Given strings s and t of length m and n respectively, return the minimum length substring of s such that every character in t is present in the substring. The substring can contain duplicate characters.

LeetCode - Rotate Image

Example:

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

Visual explanation of valid substring windows and the minimum one

BANC is the minimum window containing all characters from t.

Brute Force

Intuition

  • Store each character’s frequency from t in a map
  • Use two nested loops to iterate over all substrings
  • Track character frequencies and a count of matched characters
  • When count == t.size(), compare against the current best answer

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> mp;
        for (char c : t) mp[c]++;

        string ans = "";
        int minLen = INT_MAX;
        int m = s.size(), n = t.size();

        for (int i = 0; i < m; i++) {
            int count = 0;
            unordered_map<char,int> temp;

            for (int j = i; j < m; j++) {
                if (mp.count(s[j]) == 0) continue;

                temp[s[j]]++;
                if (temp[s[j]] <= mp[s[j]])
                    count++;

                if (count == n) {
                    int len = j - i + 1;
                    if (len < minLen) {
                        ans = s.substr(i, len);
                        minLen = len;
                    }
                }
            }
        }

        return ans;
    }
};

Complexity

Time - O(m²) Space - O(m + n)

This gives TLE when s and t are large. We need an O(m + n) solution. Also the subtr take k time.

Optimal Approach — Sliding Window

Intuition

  • Expand the right pointer until the window contains all characters of t
  • Then shrink from the left while all characters of t are still present
  • Track the best valid window using start and minLen instead of extracting the substring on every update

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> mp;
        for (char c : t) mp[c]++;

        int n = t.size(), m = s.size();
        int i = 0, j = 0, count = 0;
        int minLen = INT_MAX, start = 0;
        unordered_map<char, int> temp;

        while (j < m) {
            if (mp.count(s[j])) {
                temp[s[j]]++;
                if (temp[s[j]] <= mp[s[j]])
                    count++;
            }
            j++;

            while (count == n) {
                int len = j - i;
                if (len < minLen) {
                    minLen = len;
                    start = i;
                }

                if (mp.count(s[i])) {
                    temp[s[i]]--;
                    if (temp[s[i]] < mp[s[i]])
                        count--;
                }
                i++;
            }
        }

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

Complexity

Time - O(m + n) Space - O(m + n)

What I Got Wrong Earlier

Instead of storing start and minLen, I was computing and storing the substring on every valid window:

1
2
3
4

if (len < minLen) {
    ans = s.substr(i, len);  //  substring extraction inside the loop
    minLen = len;
}

s.substr() is O(len) and calling it repeatedly caused TLE. Instead of this we store the starting index of substring and compute the substring once at the end.

Key Takeaways

  • Minimize unnecessary computation inside hot loops — defer substr extraction to the end
  • Sliding window problems follow an almost identical pattern: expand right, shrink left, track the best state