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)

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

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.

Rust Solution

Rust's HashMap<char, i32> needs its value type spelled out where JS just infers it, and *map.entry(c).or_insert(0) += 1 counts each char in a single expression — entry inserts 0 on first sight, then the * deref increments in place. A String can't be indexed by position, so the code collects s.chars() into a Vec<char> up front to make s_chars[end] an O(1) lookup. map.get_mut(&ec) yields Some(cnt) only for characters t actually tracks, so the if let both borrows the slot mutably and skips irrelevant chars in one move, and usize::MAX stands in for JS's Infinity. The window is rebuilt with s.chars().skip(head).take(min_len).collect() rather than a byte slice, keeping it correct for multi-byte characters.

Go Solution

The map is keyed by byte (map[byte]int{}), so indexing the string with t[i] and s[end] yields the raw bytes it counts — fine for this ASCII input, but not Unicode-aware the way Rust's char keys are. The comma-ok form cnt, ok := m[ec] pulls double duty: ok gates whether the character is one t needs, while the count is read into a local, mutated, then written back with m[ec] = cnt. Rather than a MAX sentinel, minLen is seeded with len(s)+1 — an impossible window width — and the final s[head : head+minLen] returns a slice view into s with no allocation, where Rust must collect a fresh String. The no-window case simply returns "".