Python Forum

Hello Everyone,

This is my first post so if do manage to do something incorrectly please let me know. The question i have is regarding time complexity. It is a basic question and i want to see if i have a proper grasp of bigO notation.

Language: Python 3
Problem: Leetcode 771

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

• Input: J = "aA", S = "aAAbbbb"
  
• Output: 3
  

Example 2:

• Input: J = "z", S = "ZZ"
  
• Output: 0
  

Note:
S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Here is my code:

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        x = 0
        for jewels in J:
            x = x + S.count(jewels)
        return(x)

**Now the time complexity (MY GUESS):
Since I traverse through J (for loop), and given J can have a length at most 50 that gives me O(J.Len) worse case. Now inside my for loop i use the count() method, which checks the occurrence of each element and its time complexity is O(n), n being the len of the string is searches. For my case S can be of len 50 at worse case. So making the time complexity of my code O(J.len) * O(S.len)or O(J.len*S.len)?

Is that correct?

Yes. But you can do it in O(len(J)) + O(len(S))

from collections import defaultdict

jewels = "aA"
stones = "aAAbbbb"
count = defaultdict(int)

for stone in stones: # O(len(stones))
    count[stone] += 1
    
for jewel in jewels: # O(len(jewels))
    try:
        print(f'{jewel}:{count[jewel]}')
    except ValueError:
        print(f'{jewel}:0')