Python Beginner Algorithms Tutorial

Jewels and Stones (via Leetcode)

Problem Statement¶

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 that 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".

Test Cases¶

Test case #1:

• Input: J = "aA", S = "aAAbbbb"
• Output: 3
• Reasonsing: The first 3 characters in S are characters that are in J

Test case #2:

• Input: J = "z", S = "ZZ"
• Output: 0
• Reasonsing: There are no instances of z in S
In [ ]:
# assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
# assert count_jewels_in_stones(J = "z", S = "ZZ") == 0


Pseudocode¶

This code uses minimal storage - a low space complexity - of just O(1) since the 1 represents the space of the variable count_jewels_in_collection.

However, this code has a high time complexity because for every element in J, I must search all elements in S. If we use the letter n to assign the length of items in J and m to assign the length of items in S, then the time complexity is O(mn).

In [1]:
# create function to take in J and S

# create a variable - a counter - to count the number of jewels found in the stones collection

# iterate over each element in J
# iterate over each item in S
#  if element is equal to item
# increment the counter by 1
# return counter


Code¶

In [3]:
def count_jewels_in_stones(J, S):
count_jewels_in_collection = 0

for element in J:
for item in S:
if element == item:
count_jewels_in_collection += 1
return count_jewels_in_collection


Let's run the assert statements below to verify the function passes these test cases.

In [4]:
assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones(J = "z", S = "ZZ") == 0


Pseudocode #2 Solution¶

The above answer had high time complexity and low space complexity. I can design an alternative solution as a tradeoff with low time complexity and high space complexity.

I will use a Python set covered in detail here in the official documentation.

In the code below, the set represents an O(n) space complexity and the variable is an O(1) space complexity.

I iterate over each element in S so my code has an O(m) time complexity.

In [6]:
# assign each letter in J to be a value in a Python set

# store a variable as a counter of occurences of J in S

# iterate over each element in S
# if element is in Python set of S characters
# append 1 to counter


Code #2 Solution¶

In [10]:
def count_jewels_in_stones2(J, S):
s_set = set(J)
count_jewels_in_collection = 0

for item in S:
if item in s_set:
count_jewels_in_collection += 1
return count_jewels_in_collection


Let's run the assert statements below to verify this new function passes these test cases.

In [11]:
assert count_jewels_in_stones2(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones2(J = "z", S = "ZZ") == 0