Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input: s1 = “ab” s2 = “eidbaooo” Output: True Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input:s1= “ab” s2 = “eidboaoo” Output: False

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

Solution

Easy approach to check string p is a permutation of string s by checking each character from p to the s. As given string is in lower case,so there are only 26 lower case letters in this problem, we can just use an array to represent the map.

Now we can apply sliding window approach to s2 string, create a sliding window with length of s1, move from beginning to the end of s2. When a character moves in from right of the window, we subtract 1 to that character count from the map. When a character moves out from left of the window, we add 1 to that character count. So once we see all zeros in the map, meaning equal numbers of every characters between s1 and the substring in the sliding window, we know the answer is true.

Code

Output

true

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *