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