Find the shortest substring of one string that contains every character from another string, including multiplicities.
Problem
Given two strings s and t, return the shortest substring of s that contains every character from t with at least the same frequency.
If no such substring exists, return an empty string.
A substring is a contiguous segment of the original string. Characters are case-sensitive and must be matched exactly.
Goal
Search through s efficiently and identify the minimum-length valid window.
Input Format
- A string
s - A string
t
Both strings contain standard ASCII characters in the common LeetCode version of this problem.
Output Format
- Return the shortest contiguous substring of
sthat contains all characters fromtwith required multiplicities. - If multiple substrings have the same minimum length, returning any one of them is acceptable.
Constraints
- The answer must be a contiguous substring of
s - Every character in
tmust appear in the window at least as many times as it appears int - If no valid window exists, return
"" - Typical interview constraints are large enough that an scan is too slow
Example 1
Input
s = "ADOBECODEBANC", t = "ABC"
Output
"BANC"
Explanation
"BANC" is the shortest substring of s containing A, B, and C.
Example 2
Input
s = "a", t = "a"
Output
"a"
Explanation
The only substring is valid.
Show 1 more example
Example 3
Input
s = "a", t = "aa"
Output
""
Explanation
s does not contain enough a characters to form a valid window.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.