Permutation in a String

Medium·Tagsstringsliding-windowhash-table

Problem Statement

Given a string and a pattern, find out if the string contains any permutation of the pattern. A permutation is defined as the re-arranging of the characters of the string. For example, "abc" has permutations "bca", "cab", "cba", etc.

Examples

Example 1

Input

pattern: "abc", str: "oidbcaf"

Output

"true"

Why

The string contains "bca" which is a permutation of the given pattern.

Example 2

Input

pattern: "dc", str: "odicf"

Output

"false"

Why

No permutation of "dc" exists in the given string.

Example 3

Input

pattern: "bcdyabcdx", str: "bcdxabcdy"

Output

"true"

Why

Both strings are permutations of each other.

Constraints

•1 <= pattern.length <= 10000
•1 <= str.length <= 100000
•Both strings consist of standard lowercase English characters.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A permutation of a string means the character frequencies must exactly match.

Hint 2

Instead of checking every substring of the pattern's length, create a sliding window of the pattern's length.

Hint 3

Keep a frequency map (or array) of the pattern. As the window slides over the string, decrement the frequency of the character entering the window and increment the frequency of the character leaving the window. If the frequencies match perfectly, you found a permutation!