Minimum window substring

Problem

Given a text s and a text t, find the shortest piece of s that contains every letter of t, including repeated letters. If several pieces have the same shortest length, print the leftmost. Print NONE if no piece works.

Input, output and limits

Input: Line 1: the text s. Line 2: the text t.
Output: The piece, or NONE.
Constraints: 1 ≤ length of s, length of t ≤ 1000
Letters are English letters; case matters

Examples

Example

Input

ADOBECODEBANC
ABC

Output

BANC

The piece "BANC" holds A, B and C and is the shortest.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Count what t needs and track how many needed letters are still missing.

Hint 2

When nothing is missing, record the piece, then drop letters from the left while it still holds everything.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Is a rearrangement inside?medium
Maximum of every stretchhard
Longest run after replacementsmedium
Steady stretchhard
Longest piece with limited lettersmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Sliding Window problems

Problem

Input, output and limits

Examples

Hints

More Sliding Window problems