Jobs

Interviews

Discussions

Jewels and Stones

#723 Most AskedEasy

Jewels and Stones #723 Most Asked

Easy

Bloomberg LP

7 views

Topics:

Strings

You're given strings jewels representing the types of stones that are jewels, and stones representing 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".

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints:

1 <= jewels.length, stones.length <= 50
jewels and stones consist of only English letters.
All the characters of jewels are unique.

Try coding it in LeetCode

Jewels and Stones

#723 Most AskedEasy

Jewels and Stones #723 Most Asked

Easy

Bloomberg LP

7 views

Topics:

Strings

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints:

1 <= jewels.length, stones.length <= 50
jewels and stones consist of only English letters.
All the characters of jewels are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `jewels` and `stones` strings contain any characters beyond standard ASCII, or should I expect only characters from the English alphabet?
Are the characters in `jewels` guaranteed to be unique, or could there be duplicate jewel types?
Are the input strings case-sensitive (e.g., is 'a' a different jewel than 'A')?
Can the input strings `jewels` or `stones` be empty or null?
What is the maximum possible length of the `jewels` and `stones` strings?

Brute Force Solution

Approach

We need to count how many stones are also jewels. The simplest way to do this is to look at each stone one by one and check if it's a jewel.

Here's how the algorithm would work step-by-step:

Take the first stone from the pile of stones.
Check if this stone is in the list of jewels.
If it is a jewel, add one to our jewel count.
Take the next stone from the pile.
Repeat steps 2 and 3 for every single stone in the pile.
Once you've checked all the stones, the jewel count is the answer.

Code Implementation

def jewels_and_stones_brute_force(jewels, stones):
    jewel_count = 0

    # Iterate through each stone to check if it is a jewel
    for each_stone in stones:

        # Check if the current stone is in the jewels string
        if each_stone in jewels:

            # Increment the jewel count if the stone is a jewel
            jewel_count += 1

    return jewel_count

Big(O) Analysis

Time Complexity

O(m*n) – The outer loop iterates through each of the 'm' stones. For each stone, the inner operation checks if that stone is present in the 'n' jewels. This check involves a search within the jewels string. Thus, for each of the 'm' stones, we perform an operation that takes O(n) time in the worst case. Therefore, the overall time complexity is O(m*n).

Space Complexity

O(1) – The provided solution iterates through the stones and checks each stone against the jewels. It appears to maintain a single jewel count, which requires constant space. No additional data structures like lists, hash maps, or recursion are used to store intermediate results or manage the iteration. Therefore, the auxiliary space used by this algorithm is constant and independent of the input size (number of jewels or stones). This results in a space complexity of O(1).

Optimal Solution

Approach

The most efficient way to solve this problem is to first identify each unique type of 'jewel' and then count how many of those jewels are present in the 'stones' you have. We avoid redundant comparisons by creating a quick way to check if a stone is a jewel.

Here's how the algorithm would work step-by-step:

First, make a list of all the different types of 'jewels'. Think of it as creating a reference set.
Then, go through each of your 'stones' one by one.
For each stone, check if it is present in your list of jewels.
If the stone is a jewel, increase your jewel count.
Continue doing this for every stone until you've checked them all.
The final count is the number of jewels you have among your stones.

Code Implementation

def jewels_and_stones(jewels, stones):    jewels_set = set(jewels)
    jewel_count = 0
    # Iterate through each stone to check if it's a jewel.
    for stone in stones:
        # Check if the current stone is present in the set of jewels.
        if stone in jewels_set:
            jewel_count += 1

    return jewel_count

Big(O) Analysis

Time Complexity

O(J+S) – The algorithm first iterates through the 'jewels' string (J) to create a set of unique jewel types. The length of this string determines the time complexity for this step, which is O(J). Next, the algorithm iterates through the 'stones' string (S), and for each stone, it checks if that stone exists in the jewel set. Checking for membership in a set takes O(1) time. Therefore, iterating through all the stones takes O(S) time. The overall time complexity is determined by the sum of these two steps, resulting in O(J + S).

Space Complexity

O(J) – The algorithm's space complexity is determined by the list of distinct 'jewels' created in step 1. This list acts as a reference set to efficiently check for the presence of a jewel. If there are J unique types of jewels, the auxiliary space used to store this list is proportional to J. Therefore, the space complexity is O(J), where J is the number of unique characters in the 'jewels' string.

Edge Cases

Case	How to Handle
jewels is null or empty	Return 0 if `jewels` is null or empty because no stones can be jewels.
stones is null or empty	Return 0 if `stones` is null or empty because there are no stones to check.
Both jewels and stones are empty strings	Return 0 as there are no jewels or stones.
jewels and stones contain very long strings (e.g., length exceeding maximum string length)	Ensure the chosen data structure (e.g., HashSet) has sufficient capacity and time complexity remains acceptable (O(n+m) using hashset).
jewels contains duplicate characters	The count will be correct since we are iterating over stones and checking if each stone is present in jewels, handling duplicate jewels without problems.
stones contains duplicate characters	Each duplicate stone will be counted if it is also a jewel; this is expected behavior.
jewels and stones contain Unicode characters	The solution should work correctly with Unicode characters assuming the language and data structures (String, Set) support them.
All stones are jewels (stones contains only characters present in jewels)	The solution should correctly count all stones as jewels, returning stones.length().

jewels is null or empty

How to Handle:

Return 0 if `jewels` is null or empty because no stones can be jewels.

stones is null or empty

How to Handle:

Return 0 if `stones` is null or empty because there are no stones to check.

Both jewels and stones are empty strings

How to Handle:

Return 0 as there are no jewels or stones.

jewels and stones contain very long strings (e.g., length exceeding maximum string length)

How to Handle:

Ensure the chosen data structure (e.g., HashSet) has sufficient capacity and time complexity remains acceptable (O(n+m) using hashset).

jewels contains duplicate characters

How to Handle:

The count will be correct since we are iterating over stones and checking if each stone is present in jewels, handling duplicate jewels without problems.

stones contains duplicate characters

How to Handle:

Each duplicate stone will be counted if it is also a jewel; this is expected behavior.

jewels and stones contain Unicode characters

How to Handle:

The solution should work correctly with Unicode characters assuming the language and data structures (String, Set) support them.

All stones are jewels (stones contains only characters present in jewels)

How to Handle:

The solution should correctly count all stones as jewels, returning stones.length().

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `jewels` and `stones` strings contain any characters beyond standard ASCII, or should I expect only characters from the English alphabet?
Are the characters in `jewels` guaranteed to be unique, or could there be duplicate jewel types?
Are the input strings case-sensitive (e.g., is 'a' a different jewel than 'A')?
Can the input strings `jewels` or `stones` be empty or null?
What is the maximum possible length of the `jewels` and `stones` strings?

Brute Force Solution

Approach

We need to count how many stones are also jewels. The simplest way to do this is to look at each stone one by one and check if it's a jewel.

Here's how the algorithm would work step-by-step:

Take the first stone from the pile of stones.
Check if this stone is in the list of jewels.
If it is a jewel, add one to our jewel count.
Take the next stone from the pile.
Repeat steps 2 and 3 for every single stone in the pile.
Once you've checked all the stones, the jewel count is the answer.

Code Implementation

def jewels_and_stones_brute_force(jewels, stones):
    jewel_count = 0

    # Iterate through each stone to check if it is a jewel
    for each_stone in stones:

        # Check if the current stone is in the jewels string
        if each_stone in jewels:

            # Increment the jewel count if the stone is a jewel
            jewel_count += 1

    return jewel_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, make a list of all the different types of 'jewels'. Think of it as creating a reference set.
Then, go through each of your 'stones' one by one.
For each stone, check if it is present in your list of jewels.
If the stone is a jewel, increase your jewel count.
Continue doing this for every stone until you've checked them all.
The final count is the number of jewels you have among your stones.

Code Implementation

def jewels_and_stones(jewels, stones):    jewels_set = set(jewels)
    jewel_count = 0
    # Iterate through each stone to check if it's a jewel.
    for stone in stones:
        # Check if the current stone is present in the set of jewels.
        if stone in jewels_set:
            jewel_count += 1

    return jewel_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
jewels is null or empty	Return 0 if `jewels` is null or empty because no stones can be jewels.
stones is null or empty	Return 0 if `stones` is null or empty because there are no stones to check.
Both jewels and stones are empty strings	Return 0 as there are no jewels or stones.
jewels and stones contain very long strings (e.g., length exceeding maximum string length)	Ensure the chosen data structure (e.g., HashSet) has sufficient capacity and time complexity remains acceptable (O(n+m) using hashset).
jewels contains duplicate characters	The count will be correct since we are iterating over stones and checking if each stone is present in jewels, handling duplicate jewels without problems.
stones contains duplicate characters	Each duplicate stone will be counted if it is also a jewel; this is expected behavior.
jewels and stones contain Unicode characters	The solution should work correctly with Unicode characters assuming the language and data structures (String, Set) support them.
All stones are jewels (stones contains only characters present in jewels)	The solution should correctly count all stones as jewels, returning stones.length().

jewels is null or empty

How to Handle:

Return 0 if `jewels` is null or empty because no stones can be jewels.

stones is null or empty

How to Handle:

Return 0 if `stones` is null or empty because there are no stones to check.

Both jewels and stones are empty strings

How to Handle:

Return 0 as there are no jewels or stones.

jewels and stones contain very long strings (e.g., length exceeding maximum string length)

How to Handle:

Ensure the chosen data structure (e.g., HashSet) has sufficient capacity and time complexity remains acceptable (O(n+m) using hashset).

jewels contains duplicate characters

How to Handle:

The count will be correct since we are iterating over stones and checking if each stone is present in jewels, handling duplicate jewels without problems.

stones contains duplicate characters

How to Handle:

Each duplicate stone will be counted if it is also a jewel; this is expected behavior.

jewels and stones contain Unicode characters

How to Handle:

The solution should work correctly with Unicode characters assuming the language and data structures (String, Set) support them.

All stones are jewels (stones contains only characters present in jewels)

How to Handle:

The solution should correctly count all stones as jewels, returning stones.length().

0/1037 Bloomberg LP questions completed

0/1037 completed