232. Smallest Window Containing All Distinct Characters of a String

Given a string s, find the smallest substring of s that contains every distinct character appearing in s at least once. If more than one substring achieves this minimum length, print the one that starts earliest (leftmost).

Input: The input is a single line containing the string s. Output: Print the smallest substring of s that contains every distinct character of s at least once.

1 <= |s| <= 10^5

Computing the target distinct-character count ONCE upfront (rather than recomputing it during the sliding window scan) is a small but important detail - it gives you a fixed, known target to compare the window's current distinct count against.

Find the shortest contiguous stretch of a string that contains every DISTINCT character the whole string has, at least once each. Brute force: Check every possible contiguous substring directly, verifying if it contains all distinct characters - this costs O(n²) or worse, too slow for large strings. Optimised: This is the exact same 'sliding window with a still-missing counter' technique used in the more general 'smallest window containing all characters of ANOTHER string' problem - here the target set is simply the string's OWN distinct characters (computed once upfront), letting the same efficient single-pass expand/shrink logic apply directly.

First find the number of distinct characters in s using a set. Then generate every possible substring of s, and for each one build a set of its characters and compare its size against the required distinct count, keeping the shortest (leftmost on ties) substring that qualifies. Since there are O(n^2) substrings and each check costs up to O(n), this is very slow but obviously correct. Time: O(n^3) Space: O(n)

Compute the total distinct-character count once, then use two pointers left and right with a frequency map: advance right, incrementing counts and tracking how many distinct characters currently have a nonzero count; whenever the window contains all distinct characters, try to shrink it from the left (decrementing counts and removing characters that drop to zero) while it stays valid, updating the best answer at each valid state. Because left and right each only move forward across the whole scan, the total work is linear. Time: O(n) Space: O(1)

For each starting index i, walk a pointer j to the right one step at a time, adding characters to a hash set, and stop as soon as the set's size equals the total distinct-character count; record that window's length. Moving to the next start index resets the set and repeats the scan. This avoids materializing and comparing full substrings, but still redoes a fresh expansion from scratch for every start. Time: O(n^2) Space: O(1)

1. First count how many distinct characters exist in the entire string - this is your target count. 2. Slide a window's right edge forward, tracking how many DISTINCT characters are currently inside it. 3. Once the window contains all distinct characters (matching the target count), try shrinking from the left as much as possible while it stays valid, recording the smallest (and leftmost, if tied) valid window found. 4. Continue expanding and shrinking until the right edge reaches the end.

Time: O(n) - one pass to find the distinct character count, one combined expand/shrink pass to find the smallest window. Space: O(alphabet size), for tracking character counts within the current window.

s where every character is already distinct (the whole string is the answer); s with a single repeated character (a short answer, potentially length 1); s up to 10^5 characters for performance.

Be ready to connect this immediately to the more general 'minimum window substring' problem (matching against ANOTHER string t) - recognizing that this is just the special case where t is 'one of each of s's own distinct characters' shows strong pattern-recognition.