Given two strings, str1 and str2, return the smallest substring of str1 that contains every character from str2 (including duplicates). If no such substring exists, return an empty string.
A substring is any contiguous sequence of characters within a string. For example, the substrings of string abc are a, b, c, ab, bc, and abc. A substring is formed by selecting a starting and ending point without skipping characters in between.
Input
str1: A string
str2: A string
Notes
If multiple solutions exist, you may return any of them
Examples
Input: str1 = "ABCD", str2 = "AC"
Output: "ABC"
Explanation: The substring 'ABC' contains both 'A' and 'C'
Input: str1 = "AAABBBCCC", str2 = "ABC"
Output: "ABBBC"
Explanation: The substring 'ABBBC' contains 'A', 'B', and 'C', making it the smallest valid substring.
Input: str1 = "A", str2 = "AA"
Output: ""
Explanation: str1 does not have enough 'A's to match the two required in str2, so the result is an empty string.
Constraints
1 <= str1.length, str2.length <= 10,000
str1 and str2 contains only uppercase English letters
Unlock the official solution for “Shortest Substring Containing Characters” so you can compare your approach, catch edge cases, and tighten your explanation.
Official solution walkthrough
Edge cases and test review
Tradeoffs and explanation tips
Loading...
Shortest Substring Containing Characters | Algorithms Interview Questions with Solutions