Permutation in String

Question

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:

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

Tags

• String
• Hash Table

Thought

Use counter to count the frequency to check the permutation.

Code

from collections import Counter

class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        counter1 = Counter(s1)
        counter2 = Counter(s2[:len(s1) - 1])
        for i in xrange(len(s1) - 1, len(s2)):
            counter2[s2[i]] += 1
            if counter1 == counter2:
                return True
            counter2[s2[i - len(s1) + 1]] -= 1
            if counter2[s2[i - len(s1) + 1]] == 0:
                del counter2[s2[i - len(s1) + 1]]
        return counter1 == counter2