Minimum Length Substring Containing All Characters

Problem Statement

Given two strings, source and target, find the smallest substring in source that includes every character from target at least once. The solution should have a time complexity of O(n).

Examples

Example 1:
sourceStr = "ZXAYBCYABZ"
targetStr = "ABC"
Expected result: "AYBC"

Example 2:
sourceStr = "HELLOWORLD"
targetStr = "LOD"
Expected result: "LOWORL"

Example 3:
sourceStr = "AABBCCDD"
targetStr = "BCD"
Expected result: "BCCDD"

Example 4:
sourceStr = "XYZ"
targetStr = "ABC"
Expected result: ""
    

Constraints

• 1 ≤ length of source ≤ 15,000
• 1 ≤ length of target ≤ 10,000
• Both source and target consist of uppercase English letters.