Minimum Window Substring (Length)
Hard About 35 min Free, no account needed
Length of the shortest window of text covering every required character.
The brief
Given strings text and chars, return the length of the shortest
contiguous window of text that contains every character of chars
(including duplicates), or 0 when no such window exists.
The obvious approach expands a fresh window from every starting position, recounting as it goes, O(n2). In the hidden test the only valid window spans nearly all of a 40,000-character string, so the quadratic version is too slow. You will need an approach where the work stays close to O(n).
Starter code
using System;
public class Solution
{
// TODO: return the length of the shortest window of text covering all of chars (with multiplicity); 0 if none.
public int MinWindowLength(string text, string chars)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Sliding window
- Grow and shrink a contiguous range while maintaining its state incrementally.
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- First Missing Positive Hard Free Find the smallest positive integer that does not appear in the array.
- Longest Well-Performing Interval Hard Free Longest stretch of days with more tiring days than easy ones.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.