CODEWITHSUNDEEP
pythontime-complexitybig-osliding-window
Sxc-Dev
Sxc-Dev

Reputation: 123

Big O time complexity of LeetCode 567

Below is my solution of LeetCode 567. https://leetcode.com/problems/permutation-in-string/

What would the Big o time complexity of code below be?

Should it not be O(n*m) because of if (pattern_map == str_map): in code?

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.

I looked at this solution 10:00 mark (https://www.youtube.com/watch?v=6gRj_FH3MsA) and they seem to be using array. I am not sure it can be O(N) time complexity

class Solution:
        def checkInclusion(self, s1: str, s2: str) -> 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

Upvotes: 2

Views: 215

Answers (2)

BrokenBenchmark
BrokenBenchmark

Reputation: 19251

It's O(n + m), where n is the length of s1 and m is equal to the length of s2. (This time analysis assumes that the size of the alphabet is fixed at 26, and that the 10^4 size bound on s1 and s2 are only to ensure that the code can be tested in a reasonable amount of time.)

The first for loop has O(n) iterations, and does a constant amount of work per iteration. So, its runtime is O(n).

The second for loop has O(m) iterations. It does constant work per iteration. Notice that the dictionaries map between letters and their counts. However, the problem statement says that "s1 and s2 consist of lowercase English letters." The size of these dictionaries are bounded by a constant (26 keys at most, to be exact), so comparing them takes constant time. Everything else in the loop takes constant time. So this loop takes O(m) time.

Thus, the runtime is O(n + m).

If we can't assume that the size of the alphabet is fixed as a constant (let a be the alphabet size), then each iteration of our second loop could take up to O(a) time. Then, our runtime would be bounded by O(n + a * m).

Upvotes: 1

Martin Munilla
Martin Munilla

Reputation: 302

yes this would be like O(N+M), but for the sake of simplicity you could just say O(N)

Upvotes: 0

Related Questions