Leetcode # 567. Permutation in String

Problem

https://leetcode.com/problems/permutation-in-string

Solution: Sliding Window

First Solution

Time Complexity: O(len(s2))
Space Complexity: O(26) ≡ O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def checkInclusion(self, s1: str, s2: str) -> bool:
    c1, c2 = Counter(s1), Counter()
    
    unsatisfied = set()
    def adjust_unsatisfied(c): # O(1)
      nonlocal unsatisfied
      if c1[c] == c2[c]:
        if c in unsatisfied:
          unsatisfied.remove(c)
      else:
        unsatisfied.add(c)

    for right in range(len(s2)):
      c2[s2[right]] += 1
      adjust_unsatisfied(s2[right])
      
      if right < len(s1) - 1: continue

      if right >= len(s1): 
        left = right - len(s1)
        c2[s2[left]] -= 1
        adjust_unsatisfied(s2[left])
      
      # print(s2[right - len(s1) + 1:right + 1], unsatisfied)
      if len(unsatisfied) == 0: return True

    return False

Refined Solution

Time Complexity: O(len(s2))
Space Complexity: O(26) ≡ O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def checkInclusion(self, s1: str, s2: str) -> bool:
    c1, c2 = Counter(s1), Counter(s2[:len(s1)])
    satisfied_alphas = 0
    for i in range(26):
      c = chr(i + 97)
      if c1[c] == c2[c]:
        satisfied_alphas += 1
    # print(s2[:len(s1)], satisfied_alphas)
    if satisfied_alphas == 26: return True

    for right in range(len(s1), len(s2)):
      c2[s2[right]] += 1
      if c1[s2[right]] == c2[s2[right]]:
        satisfied_alphas += 1
      # c1[c] == c2[c] -> c1[c] != c2[c]
      # <=> c2[c]: c1[c] -> c1[c] + 1
      elif c2[s2[right]] == c1[s2[right]] + 1:
        satisfied_alphas -= 1

      left = right - len(s1)
      c2[s2[left]] -= 1
      if c1[s2[left]] == c2[s2[left]]:
        satisfied_alphas += 1
      # c1[c] == c2[c] -> c1[c] != c2[c]
      # <=> c2[c]: c1[c] -> c1[c] - 1
      elif c2[s2[left]] == c1[s2[left]] - 1:
        satisfied_alphas -= 1
      
      # print(s2[right - len(s1) + 1:right + 1], satisfied_alphas)
      if satisfied_alphas == 26: return True

    return False

Last Updated on 2023/09/10 by A1go