Is Jewels and Stones easy or hard?

Jewels and Stones is categorized as an Easy problem. The challenge focuses on recognizing that repeated membership checks should use a hash-based structure instead of nested loops.

How to solve Jewels and Stones in O(n)?

Treat the jewels string as a lookup structure. Store each jewel character in a hash set, then iterate through stones and increment a counter whenever a character exists in the set. Each membership check is O(1) on average, so the total runtime becomes O(n + m).

What is the best approach for Jewels and Stones?

The hash set approach is the most common solution. Insert all characters from the jewels string into a set, then scan the stones string and count characters that appear in the set. This gives O(n + m) time complexity with O(m) extra space and keeps the implementation simple across languages.

What data structure is used in Jewels and Stones?

The most common data structure is a hash set (or hash table) used for constant-time membership checks. Some implementations also use a fixed-size boolean array indexed by character code when the character set is known.

What is the time complexity of Jewels and Stones?

The optimal solution runs in O(n + m) time, where n is the length of the stones string and m is the length of the jewels string. Building the lookup structure takes O(m), and scanning all stones requires O(n).

Is Jewels and Stones asked at Google, Amazon, or Meta?

Jewels and Stones is a common introductory interview problem used by companies such as Amazon and Google to test basic understanding of hash sets and string iteration. It checks whether candidates recognize constant-time lookup patterns.

Description Hints 1 Solution Video 6:52

771. Jewels and Stones

Easy89.5% acceptance6 companies

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.

Asked at 6 companies

Amazon Bloomberg

Google Microsoft Meta Yandex

Topics

Hash Table String

Hints open one at a time

Hint 1

For each stone, check if it is a jewel.

6:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numJewelsInStones(self, jewels: str, stones: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aA"
"aAAbbbb"

Input

"z"
"ZZ"

Your code is saved on this device.Solution