Get full access

Shortest Substring Containing Characters

Languages

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

Loading editor