Jewels and Stones

Problem Description

You are given two strings: jewels and stones. The jewels string represents the types of stones that are considered jewels. The stones string represents the stones you have. Your task is to determine how many of the stones you have are also jewels. Case matters, so 'a' is considered a different type of stone from 'A'.

For example:

• If jewels = "aA" and stones = "aAAbbbb", the output should be 3.
• If jewels = "z" and stones = "ZZ", the output should be 0.

Brute Force Solution

A naive approach is to iterate through each stone in the stones string and, for each stone, check if it is present in the jewels string. If it is, increment a counter.

Code (Python)

def num_jewels_in_stones_brute_force(jewels: str, stones: str) -> int:
    count = 0
    for stone in stones:
        if stone in jewels:
            count += 1
    return count

Time Complexity

O(m * n), where n is the length of the stones string and m is the length of the jewels string. For each of the n stones, we potentially iterate up to m times to see if it is a jewel.

Space Complexity

O(1). We use only a constant amount of extra space.

Optimal Solution

An optimal approach is to use a hash set (or a set in Python) to store the jewels. Then, iterate through the stones string and check if each stone is present in the set. This allows for O(1) lookups, improving overall performance.

Code (Python)

def num_jewels_in_stones_optimal(jewels: str, stones: str) -> int:
    jewel_set = set(jewels)
    count = 0
    for stone in stones:
        if stone in jewel_set:
            count += 1
    return count

Time Complexity

O(m + n), where n is the length of the stones string and m is the length of the jewels string. Building the jewel_set takes O(m) time, and iterating through the stones takes O(n) time. The lookup in the hash set is O(1) on average.

Space Complexity

O(m), where m is the length of the jewels string. This is because we store the characters of jewels in a hash set.

Edge Cases

• Empty jewels string: The function should return 0, as no stones can be jewels.
• Empty stones string: The function should return 0, as there are no stones to check.
• jewels and stones containing the same characters: The function should correctly count the number of stones that are also jewels.
• Case sensitivity: The function should differentiate between uppercase and lowercase letters.