Algorithms Problem Solving: Jewels and Stones

This post is part of the Algorithms Problem Solving series. And it was originally published at TK's blog.

Problem description

This is the Jewels and Stones problem. The description looks like this:

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

Examples

# input: J = "aA" | S = "aAAbbbb"
# output: 3

# input: J = "z", S = "ZZ"
# output: 0

Solution

At first, I tried to understand some corner cases. For example, what should I return if the J or the S is an empty string?

As my first solution, the brute force solution, I needed to look through the string. So I didn't need to care about the empty strings. For empty strings, it doesn't loop, it just returns the default counter, in this case, 0.

I just needed to loop through the J and for each character in the J string, I need to compare to each character of S. If they match, I increment the counter.

After looping through each character, just return the final counter.

def num_jewels_in_stones(J, S):
    jewels = 0

    for j in J:
        for s in S:
            if s == j:
                jewels += 1

    return jewels

print(num_jewels_in_stones("aA", "aAAbbbb")) # 3
print(num_jewels_in_stones("z", "ZZ")) # 0

This is a O(N^2) solution in terms of time complexity. Or more precisaly: O(len(J) * len(S)). For the space complexity, it is O(1) as we just store the value in a counter. If len(J) or len(S) increase, the used space keeps constant.

Just to iterate this solution, we can make it O(N) in terms of time complexity by using a hash table to store all characters as key and the counter as value.

def num_jewels_in_stones_opt(J, S):
    chars_counter = {}
    counter = 0

    for char in J:
        if char in chars_counter:
            chars_counter[char] += 1
        else:
            chars_counter[char] = 1

    for char in S:
        if char in chars_counter:
            counter += chars_counter[char]

    return counter

print(num_jewels_in_stones_opt("aA", "aAAbbbb")) # 3
print(num_jewels_in_stones_opt("z", "ZZ")) # 0

So, for each J's character. Verify if it is already in the chars_counter. If it is, just increment it. If not, initialize the counter.

Then, for each S's character, verify if this character is in the chars_counter. If it is, get it and add to the counter variable. If not, do nothing.

After this iteration, we need the final value of the counter. Just return it.

As we said before, it runs in O(N). Better than the first solution. But, for the worst-case scenario, the space complexity is O(N), worse than the first approach.

---

For more stories and posts about my journey learning & mastering software engineering, take a look at what I've been writing and documenting.

My Twitter & Github. ☺

Resources

• Learning Python: From Zero to Hero
• One Month Python Course
• Big-O Notation For Coding Interviews and Beyond
• Learn Python from Scratch
• Learn Object-Oriented Programming in Python
• Data Structures in Python: An Interview Refresher

Comments

[Musale Martin]

Nice article. I wonder what the impact of using the collections.Counter package has on the second solution? So instead of initializing the chars_counter to a dict, you initialize it to the collections.Counter in-built for J's characters.

[ArcticSpaceFox]

Cool series, but I wanna solve the problem before reading your solution. Hope to see more coming but no stress 👍

[TK]

Thanks! I have 10 more posts to publish. I just need to organize them and I'll definitely publish them here :)

[ArcticSpaceFox]

Hmm weird, during testing of both algorithms they take the same amount of time, do you see why that is? I test them on 10 Million random chars of aAbB

[TK]

I think it is because you are running with short length strings (aAbB). The first solution will be very slow for the worst-case scenario, where the string has a long length.

Imagine this example: strings with 10,000 chars.

The first solution has a nested for. The combination of each character would be 10,000 * 10,000 = 100,000,000.

The second solution has two for, but not nested. It would be 10,000 + 10,000 = 20,000 for the worst-case scenario.

The curve increases differently for each solution. Did it make sense to you?

Just for curiosity: how are you testing the amount of time spent by each algorithm?

[ArcticSpaceFox]

I use timeit and measure time before and after. Thank you I will try to modify my file which is tested on