Minimum Window Substring for Required Characters

MediumArrayStringSliding WindowHashingFrequency CountTwo Pointers

You are given two strings S and T. Find the smallest substring in S that contains all characters of T (including frequency). If no such substring exists, return an empty string. If multiple answers exist, return any one. This problem simulates searching the smallest valid data segment that satisfies all required conditions.

Why this is asked

Tests sliding window deeply
Real use: search/filter systems

Example

Input:

S = ADOBECODEBANC

T = ABC

Output:

BANC

Examples

Example 1

Input: MYNAMEISJEFF,MJ

Output: MYNAMEISJ

Example 2

Input: ADOBECODEBANC,ABC

Output: BANC

Example 3

Input: AZOBECODEBANC,ABC

Output: BANC

Loading...

Input:

MYNAMEISJEFF,MJ

Expected Output:

MYNAMEISJ

Minimum Window Substring for Required Characters

Why this is asked

Example

Input:

Output:

Examples

Hint 1

Hint 2