A pantry log lists, in order, the ingredient letter used at each step of a cooking session, as a string s of uppercase letters. A recipe requires a multiset of ingredient letters, given as a string r (e.g. r = "AAB" requires at least two As and one B). Find the length of the shortest contiguous window of s that contains, for every letter appearing in r, at least as many occurrences as r requires. If no such window exists, print -1.
Input format
Line 1: a non-empty string s (the pantry log), uppercase letters only.
Line 2: a non-empty string r (the recipe requirement), uppercase letters only.
Output format
A single integer: the length of the shortest window of s covering the multiset of r, or -1 if no such window exists.
Constraints
- 1 ≤ |s| ≤ 100000
- 1 ≤ |r| ≤ 100000
- Both strings contain only uppercase letters
A-Z.