LC 0567 [M] Permutation in String - ALawliet/algorithms GitHub Wiki
if s1 (shorter string) is a permutation (anagram) in s2 (longer string)
freq hashmap is the s1 chars found so far in s2, so when freq_s1[s2_c] == 0, then we have a match for that char
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq = Counter(s1) # the count remaining that wasn't matched
w = len(s1)
match_combo = 0
for r in range(len(s2)):
if s2[r] in freq:
cr = s2[r]
freq[cr] -= 1 # (do) 1st
if freq[cr] == 0: match_combo += 1 # 2nd
l = r - w
if r >= w: # r > w - 1, window bigger than s1, start sliding
if s2[l] in freq:
cl = s2[l]
if freq[cl] == 0: match_combo -= 1 # (undo reverse) 2nd
freq[cl] += 1 # 1st
if match_combo == len(freq):
return True
return False
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq = Counter(s1)
w = len(s1)
match_combo = 0
for r in range(len(s2)):
if s2[r] in freq:
cr = s2[r]
if not freq[cr]: match_combo -= 1
freq[cr] -= 1
if not freq[cr]: match_combo += 1
l = r - w
if r >= w:
if s2[l] in freq:
cl = s2[l]
if not freq[cl]: match_combo -= 1
freq[cl] += 1
if not freq[cl]: match_combo += 1
if match_combo == len(freq):
return True
return False
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
freq1 = Counter(s1)
freq2 = Counter(s2[:len(s1)])
if freq2 == freq1: return True
l = 0
for r in range(len(s1), len(s2)):
freq2[s2[r]] += 1
freq2[s2[l]] -= 1
if freq2[s2[l]] == 0: freq2.pop(s2[l])
l += 1
if freq2 == freq1: return True
return False
def find_permutation(str1, pattern):
l, matched = 0, 0
freq = Counter(pattern)
# our goal is to match all the characters from the 'char_frequency' with the current window
# try to extend the range [window_start, window_end]
for r in range(len(str1)):
if str1[r] in freq:
# decrement the frequency of matched character
freq[str1[r]] -= 1
if freq[str1[r]] == 0:
matched += 1
if matched == len(freq):
return True
# shrink the window by one character
if r >= len(pattern) - 1:
l += 1
if str1[l] in freq:
if freq[str1[l]] == 0:
matched -= 1
freq[str1[l]] += 1
return False