LC567 - Permutation in String

Problem

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

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: s2 contains one permutation of s1 ("ba").

Solution

Time complexity is $O(n)$, with constant $O(1)$ space used.

def checkInclusion(self, s1: str, s2: str) -> bool:
	if len(s1) > len(s2):
		return False
	# 26 eng chars
	s1Counts, s2Counts = [0] * 26, [0] * 26
	
	for i in range(len(s1)):
	
	# ASCII val of char, to build char count in array. ord('a') is offset of a from zero.
		s1Counts[ord(s1[i]) - ord('a')] += 1
		s2Counts[ord(s2[i]) - ord('a')] += 1
		
	if s1Counts == s2Counts:
		return True
	
	for i in range(len(s1), len(s2)):
		s2Counts[ord(s2[i]) - ord('a')] += 1
		s2Counts[ord(s2[i-len(s1)]) - ord('a')] -= 1
		if s1Counts == s2Counts:
			return True
	
	return False