Minimum Window Substring Length

You are given two strings: a string S and a pattern P. Your task is to find the length of the smallest substring of S that contains all the characters of P (including duplicates). If no such substring exists, output -1.

Formally, let the substring be denoted by S[i...j]. This substring is valid if for every character c in P, the number of occurrences of c in S[i...j] is at least as many as in P. If a valid substring exists, you should output its length, i.e. j-i+1. Otherwise, output -1.

In mathematical notation, if we denote the frequency of a character c in a string X by f_X(c), we require $$ \forall c \in P,\quad f_{S[i...j]}(c) \ge f_P(c). $$

Note that if either string is empty, or if the pattern P cannot be found in S, then the answer should be -1.

inputFormat

The input is given via standard input and consists of two lines:

1. The first line contains the string S.
2. The second line contains the pattern string P.

Both strings may contain spaces and other printable characters.

outputFormat

Output a single integer representing the length of the smallest substring of S that contains all the characters of P. If such a substring does not exist, output -1.

ADOBECODEBANC
ABC

4