Skip to main content
Talentd

Jewels and Stones - Solution & Explanation

EasyHash TableString15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive two strings: jewels and stones. Each character represents a type of stone. Characters in jewels are the types considered valuable. The task is to count how many characters in stones also appear in jewels. Matching is case-sensitive, so 'a' and 'A' represent different types.

Approach 1: Using a Set for Fast Lookup (O(n + m) time, O(m) space)

The cleanest solution uses a hash set. First insert every character from jewels into a set. This preprocessing step takes O(m) time where m is the length of the jewels string. Then iterate through the stones string and check if each character exists in the set. Hash set membership checks run in O(1) average time, so scanning n stones gives a total time complexity of O(n + m). The extra memory used by the set is O(m). This approach works well because it converts repeated string comparisons into constant-time lookups using a hash table. For most interview settings, this is the expected solution since it is both simple and optimal.

Approach 2: Using Array for Character Indexing (O(n + m) time, O(1) space)

If the character set is limited (for example ASCII letters), an indexed array can replace the hash set. Create a boolean array where each index corresponds to a character code. Iterate through jewels and mark the corresponding indices as true. Next, iterate through stones; for each character, compute its index and check whether it was marked. Increment the count whenever a marked index is found. This approach still runs in O(n + m) time but uses constant space O(1) because the array size is fixed. It avoids hashing overhead and can be slightly faster in lower-level languages like C or C++. The logic relies on direct character indexing within a string.

Recommended for interviews: The hash set solution is the one interviewers usually expect. It demonstrates that you recognize the pattern of converting repeated membership checks into constant-time lookups using a hash table. Mentioning the array-index optimization shows deeper awareness of character constraints and memory tradeoffs, but the set-based approach is typically the clearest and most portable across languages.

Approach 1: Using a Set for Fast Lookup

This approach leverages a Set (or a HashSet in some languages) for quickly determining if a stone is a jewel. The idea is to store all the jewel types in a set, then iterate through each stone, checking if the stone is in the set. If it is, we increment our count of jewels found.

In the C implementation, we define a helper function isJewel that checks if a character is a jewel by iterating through the jewel string. For each stone, we call this function and increment our count accordingly. This is not the most optimized as it involves iterating through the jewels for each stone.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings.

Try this approach in the editor →

Approach 2: Using Array for Character Indexing

This approach uses an array to quickly map each character to an index, allowing us to count frequencies of jewels in the stones. Since the input is restricted to English letters, a fixed-size array of 52 (for each upper and lower case letter) is adequate.

This C solution uses an array of size 52 to represent each letter as a potential jewel. This approach handles both uppercase and lowercase characters distinctly, using ASCII arithmetic to map letters to indices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping.

Try this approach in the editor →

Approach 3: Hash Table or Array

We can first use a hash table or array s to record all types of jewels. Then traverse all the stones, and if the current stone is a jewel, increment the answer by one.

Time complexity is O(m+n), and space complexity is O(|\Sigma|), where m and n are the lengths of the strings jewels and stones respectively, and \Sigma is the character set, which in this problem is the set of all uppercase and lowercase English letters.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Set for Fast Lookup

Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings.

Using Array for Character Indexing

Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping.

Hash Table or Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set for Fast LookupO(n + m)O(m)General case. Clean and language-agnostic solution using hash set membership checks.
Array Character IndexingO(n + m)O(1)When the character set is fixed (ASCII/letters). Slightly faster and memory-predictable.

Video Solution

Jewels and Stones - Leetcode 771 - Hashmaps & Sets (Python) • Greg Hogg • 25,078 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Jewels and Stones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters