perm-in-string.py (1619B)
1 class Solution: 2 3 # SLIDING WINDOW: 4 5 # CONSIDER: 6 7 # if s2 contains a permutation of s1 then 8 # there exists a contiguous string s1_x 9 # such that the count of each character 10 # in s1_x is the same s2 11 12 # Given this, we slide a window over s2, 13 # keeping track of character counts as we go 14 # if the characters match s1's characters, we return 15 # true. 16 17 # since we do at most 26 comparisons (one for each character) 18 # per window, we see this is O(n) 19 20 def checkInclusion(self, s1: str, s2: str) -> bool: 21 22 if len(s2) < len(s1): 23 return False 24 25 s1_counts = [0] * 26 26 s2_counts = [0] * 26 27 28 for char in s1: 29 s1_counts[to_int(char)] += 1 30 31 left_ptr = 0 32 right_ptr = len(s1) - 1 33 34 # initialize first window 35 for i in range(0, right_ptr + 1): 36 s2_counts[to_int(s2[i])] += 1 37 38 while right_ptr < len(s2): 39 # check count 40 41 if compare_lists(s2_counts, s1_counts): 42 return True 43 else: 44 s2_counts[to_int(s2[left_ptr])] -= 1 45 left_ptr += 1 46 47 right_ptr += 1 48 49 if right_ptr >= len(s2): 50 return False 51 52 s2_counts[to_int(s2[right_ptr])] += 1 53 54 return False 55 56 57 def to_int(char): 58 return ord(char) % 97 59 60 61 # assumes len(ls1) == len(ls2) which should 62 # be true when initialized to represent lower case 63 # characters. 64 65 66 def compare_lists(ls1, ls2): 67 for i in range(0, len(ls1)): 68 if ls1[i] != ls2[i]: 69 return False 70 return True