Permutation in String
Problem Statement:
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").
Intuition:
Get the counts for s1 and iterate over s2, maintaining a window of size len(s1) and check for the window over s2 if the counts are matching with s1's counts.
It's time complexity would be O(n*m), where n and m are the length of s1 and s2.
Note: The O(m) complexity was due matching of counts of
s1to every correct window.
This can be avoided by maintaining a invariant(need)
Initially:
need = len(s1)
When you add a useful character →need -= 1
When you remove a useful character →need += 1
Ifneed == 0→ permutation found ✅
Code:
My Solution - O(n*m)
def checkInclusion(s1: str, s2: str) -> bool:
s1_C = Counter(s1)
l = 0
window = len(s1)
s2_C = defaultdict(int)
for r in range(len(s2)):
s2_C[s2[r]] += 1
if r - l + 1 > window:
s2_C[s2[l]] -= 1
l += 1
if r - l + 1 == window:
found = True
for key, value in s1_C.items():
if key not in s2_C or s2_C[key] != value:
found = False
break
if found:
return True
return False
Optimal Solution - O(n)
def checkInclusion(s1, s2):
s1_C = Counter(s1)
window = need = len(s1)
l = 0
for r in range(len(s2)):
if r - l + 1 > window:
if s2[l] in s1_C:
if s1_C[s2[l]] >= 0:
need += 1
s1_C[s2[l]] += 1
l += 1
if s2[r] in s1_C:
if s1_C[s2[r]] > 0:
need -= 1
s1_C[s2[r]] -= 1
if need == 0:
return True
return False