Jewels and Stones

Easy

Amazon

1 view

Topics:

Strings

You are given two strings, jewels and stones. The string jewels represents the types of stones that are jewels, and stones represents the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, 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.

Write a function that takes two strings, jewels and stones, as input and returns the number of stones that are also jewels. Explain the time and space complexity of your solution. Discuss any edge cases that need to be considered.

Jewels and Stones

Easy

Amazon

1 view

Topics:

Strings

Letters are case sensitive, 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.

Solution

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. Note that letters are case-sensitive.

Naive Solution

A straightforward approach is to iterate through 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_naive(jewels: str, stones: str) -> int:
    count = 0
    for stone in stones:
        if stone in jewels:
            count += 1
    return count

Time Complexity

O(J * S), where J is the length of the jewels string and S is the length of the stones string. This is because, for each stone in stones, we potentially iterate through the entire jewels string to check if it's a jewel.

Space Complexity

O(1). We're only using a constant amount of extra space for the count variable.

Optimal Solution

To improve the time complexity, we can use a set to store the jewels. This allows us to check if a stone is a jewel in O(1) time on average.

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(J + S), where J is the length of the jewels string and S is the length of the stones string. Creating the jewel_set takes O(J) time, and iterating through the stones string takes O(S) time.

Space Complexity

O(J), where J is the length of the jewels string. This is because we are storing the jewels in a set.

Edge Cases

Empty strings: If either jewels or stones is an empty string, the code should still function correctly and return 0 if stones is empty, or 0 if jewels is empty because no stones can be jewels.
Duplicate jewels: The problem states that all characters in jewels are unique, so we don't need to handle this case.
Case sensitivity: The problem specifies that the characters are case-sensitive, so 'a' and 'A' are considered different types of stones, which is handled correctly by both solutions.

Solution

Jewels and Stones

Problem Description

Naive Solution

A straightforward approach is to iterate through 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_naive(jewels: str, stones: str) -> int:
    count = 0
    for stone in stones:
        if stone in jewels:
            count += 1
    return count

Time Complexity

Space Complexity

O(1). We're only using a constant amount of extra space for the count variable.

Optimal Solution

To improve the time complexity, we can use a set to store the jewels. This allows us to check if a stone is a jewel in O(1) time on average.

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(J + S), where J is the length of the jewels string and S is the length of the stones string. Creating the jewel_set takes O(J) time, and iterating through the stones string takes O(S) time.

Space Complexity

O(J), where J is the length of the jewels string. This is because we are storing the jewels in a set.

Edge Cases

Empty strings: If either jewels or stones is an empty string, the code should still function correctly and return 0 if stones is empty, or 0 if jewels is empty because no stones can be jewels.
Duplicate jewels: The problem states that all characters in jewels are unique, so we don't need to handle this case.
Case sensitivity: The problem specifies that the characters are case-sensitive, so 'a' and 'A' are considered different types of stones, which is handled correctly by both solutions.