title: Big O time complexity of LeetCode 567
body: <p>Below is my solution of LeetCode 567. <a href="https://leetcode.com/problems/permutation-in-string/" rel="nofollow noreferrer">https://leetcode.com/problems/permutation-in-string/</a></p>
  <p>What would the Big o time complexity of code below be?</p>
  <p>Should it not be O(n*m) because of if (pattern_map == str_map): in code?</p>
  <p>Edit: n = pattern_map, m = str_map
  Edit 1: As stated is accepted answer, the correct values are n = length of s1 and m = length of s2.</p>
  <p>I looked at this solution 10:00 mark (<a href="https://www.youtube.com/watch?v=6gRj_FH3MsA" rel="nofollow noreferrer">https://www.youtube.com/watch?v=6gRj_FH3MsA</a>) and they seem to be using array. I am not sure it can be O(N) time complexity</p>
  <pre><code>class Solution:
          def checkInclusion(self, s1: str, s2: str) -&gt; bool:
              
              pattern = s1
              str = s2
              
              pattern_map = {}
              str_map = {}
      
              for i in range(len(pattern)):
                  patt_char = pattern[i]
                  pattern_map[patt_char] = 1 + pattern_map.get(patt_char, 0)
      
              window_start = 0
              for i in range(len(str)):
                  right_char = str[i]
                  str_map[right_char] = 1 + str_map.get(right_char, 0)
      
                  length_of_window = i-window_start+1
                  if length_of_window == len(pattern):
                      left_char = str[window_start]
                      if (pattern_map == str_map):
                          return True
                      str_map[left_char] = str_map[left_char] - 1
      
                      if str_map[left_char] == 0:
                          del str_map[left_char]
      
                      window_start += 1
              
              return False
  </code></pre>