Minimum Window Substring

In this coding challenge, your task is to find the smallest substring in a given string that contains all the characters of another string. This challenge is like finding a hidden treasure map that shows you the shortest path to gather all the treasure! It's a fun and engaging puzzle that can help develop logical thinking and problem-solving skills.

Imagine you have a string S and you need to create a treasure map using another string T which contains all the treasures you need. Your goal is to find the shortest path in S that picks up all the treasures (characters of T).

Let's see some examples:

Examples

# Example 1
generate_map("ADOBECODEBANC", "ABC")
# This should return "BANC", as it is the smallest window that contains 'A', 'B', and 'C'.

# Example 2
generate_map("XYXYYXYZ", "XYZ")
# This should return "XYZ", since 'X', 'Y', and 'Z' first appear in this shortest sequence.

# Example 3
generate_map("a", "aa")
# This should return "", because there's not enough 'a' to fulfill the treasure map requirements.

Your task is to implement the function generate_map(S: str, T: str) -> str that achieves this. If there is no such window, return an empty string "".

Grab your coding backpack and start the adventure!