567. Permutation in String

February 11, 2022

Given two strings s1 and s2, return true__ if __s2__ contains a permutation of __s1__, or __false__ otherwise__. In other words, return true if one of s1’s permutations is the substring of s2.

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

Constraints:

1 <= s1.length, s2.length <= 104 s1 and s2 consist of lowercase English letters.

code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2): return False
        c1 = [0] * 26
        c2 = [0] * 26
        
        for c in s1:
            c1[ord(c) - ord('a')] += 1
            
        for i, c in enumerate(s2):
            c2[ord(c) - ord('a')] += 1
            if i >= len(s1) - 1:
                if c1 == c2: return True
                c2[ord(s2[i - len(s1) + 1]) - ord('a')] -= 1
        return False

code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2): return False
        cs1 = [0] * 26
        cs2 = [0] * 26
        
        for i in range(len(s1)):
            cs1[ord(s1[i]) - ord('a')] += 1
            cs2[ord(s2[i]) - ord('a')] += 1
        
        if cs1 == cs2: return True
        
        for i in range(0, len(s2) - len(s1)):
            cs2[ord(s2[i + len(s1)]) - ord('a')] += 1
            cs2[ord(s2[i]) - ord('a')] -= 1
            if cs1 == cs2: return True

        return False