233. Smallest Window in a String Containing All Characters of Another String

Given strings s and t, find the smallest contiguous substring of s that contains every character of t, including repeated characters at least as many times as they occur in t. If more than one substring of that minimum length qualifies, print the one that starts earliest. If no such window exists, print -1.

Input: The first line contains string s. The second line contains string t. Output: Print the smallest substring of s containing all characters of t with required multiplicities, or print -1 if none exists.

1 <= |s|, |t| <= 10^5

If t is longer than s, or requires more of some character than s contains in total, no valid window can EVER exist - checking this upfront (or letting the missing-count simply never reach zero) correctly handles that impossible case.

Find the shortest stretch of one string that contains every character of another string, including enough copies of repeated characters. Brute force: Check every possible substring of s directly, verifying if it contains all of t's characters with the right counts - this costs O(n² ) or worse, too slow for large strings. Optimised: A sliding window with a 'characters still missing' counter lets both the right-edge expansion and left-edge shrinking happen in a SINGLE combined linear pass - every character is added to the window and removed from it at most once across the whole algorithm, giving true O(n+m) total work despite looking like nested loops.

Maintain a frequency map of the characters t still needs and a counter of how many distinct required characters are currently fully satisfied in the window. Expand the right pointer one character at a time, updating the map and counter in O(1); once all requirements are satisfied, shrink the left pointer as far as possible while the window remains valid, updating the same counters incrementally and recording the smallest valid window (earliest one on ties, since left only ever moves forward). Because both pointers only move forward across the whole string and each character's counts are updated in constant time, the total work is linear. Time: O(n + m) Space: O(k)

Use a left and right pointer over s, and for each left position, extend right until the current window covers all of t's characters (checked by comparing frequency counts of the window against t's requirement), then record the window length if it's the smallest so far, and move left forward. The key improvement over full substring enumeration is that only two pointers advance forward through the string rather than exploring every possible substring boundary pair, but coverage is still checked by rescanning/comparing frequency tables at each step rather than incrementally, giving quadratic behavior in the worst case. Time: O(n^2) Space: O(1)

Generate every possible substring of s (via two nested loops over start and end indices), and for each one, count its character frequencies and check whether it covers every character of t at least as many times as t requires. Track the shortest substring found that satisfies this, breaking ties by earliest start. This checks the definition directly but redoes frequency counting from scratch for every one of the O(n^2) substrings, making it far too slow for large inputs. Time: O(n^2 * 26) Space: O(1)

1. Build a frequency map of exactly what's needed from t (how many of each character). 2. Slide a window's right edge forward through s, decreasing a 'still missing' counter whenever a needed character is collected. 3. The moment the window contains everything needed (missing count reaches zero), try shrinking from the LEFT as much as possible while it stays valid - each valid shrink is a candidate for the smallest window so far. 4. Continue expanding and shrinking until the right edge reaches the end of s.

Time: O(|s| + |t|) - one pass to build t's frequency map, one combined expand/shrink pass over s. Space: O(|t| + alphabet size), for the frequency maps tracking what's needed and what's currently in the window.

t longer than s (impossible, -1); t requiring more of some character than s contains in total (-1); repeated characters in t needing matching multiplicity in the window; s, t up to 10^5 characters for performance.

This is one of the most famous 'hard' sliding window problems - be ready to clearly explain the 'missing count' technique (rather than re-checking full frequency map equality at every step, which would be much slower).