Jewels and Stones
Problem
Given two strings jewels and stones, return the number of stones that are also jewels.
- 1 ≤ jewels.length, stones.length ≤ 50
- jewels and stones consist of only English letters
- All characters in jewels are distinct
Example
jewels = "aA", stones = "aAAbbbb"3The algorithm first converts the string jewels into a set for O(1) membership checks. For the stones string, it iterates through each character and checks if it is in the jewel set. Here, 'a' and 'A' are jewels. The stones string contains 'a', 'A', 'A', and four 'b's. Only the 'a' and two 'A's count as jewels, totaling 3.
Approach
Straightforward Solution
A naive approach would check each stone character against every jewel character, resulting in O(n*m) time complexity, which is inefficient for larger inputs.
Core Observation
The problem reduces to counting how many characters in stones are members of the jewels set. Membership queries must be efficient to avoid O(n*m) complexity where n and m are lengths of stones and jewels respectively.
Path to Optimal
Converting jewels into a hash set allows O(1) average-time membership checks. This transforms the problem into a single pass over stones, checking membership in constant time, reducing complexity to O(n + m).
Optimal Approach
PreviewBuild a set from jewels for constant-time membership checks. Iterate through stones, incrementing a counter each time a stone is found in the jewel set…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + m)
Creating the set from jewels takes O(m), iterating through stones takes O(n), and each membership check is O(1) on average, resulting in linear time overall.
Space
O(m)
The set stores all unique jewel characters, which is at most the length of jewels, requiring O(m) auxiliary space.
Pattern Spotlight
Hash Maps (Set Membership for Counting)
When counting occurrences constrained by membership in a subset, transform the subset into a hash set to enable O(1) membership queries, converting nested membership checks into a single linear pass.
Solution
| 1 | class Solution: |
| 2 | def numJewelsInStones(self, jewels: str, stones: str) -> int: |
| 3 | jewel_set = set(jewels) |
| 4 | jewel_count = 0 |
| 5 | |
| 6 | for stone in stones: |
| 7 | if stone in jewel_set: |
| 8 | jewel_count += 1 |
| 9 | |
| 10 | return jewel_count |
Step-by-Step Solution
Build a Set of Jewels for Constant-Time Membership
| 3 | jewel_set = set(jewels) |
Objective
To create a hash set from the jewels string that allows O(1) average-time membership queries.
Key Insight
Using a set data structure transforms the problem from repeated linear searches for each stone character into constant-time membership checks. This is the key optimization that reduces the overall time complexity from quadratic to linear.
Interview Quick-Check
Core Logic
The set stores all jewel characters, enabling constant-time membership checks during iteration over stones.
Common Pitfalls & Bugs
Using a list or string for membership checks leads to O(n*m) time complexity, which is inefficient for larger inputs.
Count Stones That Are Jewels via Single Pass
To iterate through each stone and increment the count if it is found in the jewel set.
Return the Total Count of Jewels Found
To output the final count of stones that are jewels after processing all stones.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 1 Critical line interviewers watch for.
jewel_set = set(jewels)Create a set from the jewels string for fast membership checks.
This line transforms the jewels string into a hash set, enabling O(1) average-time membership queries, which is essential for efficient counting.
Full line-by-line criticality + rationale for all 6 lines available on Pro.
Test Your Understanding
Why is it more efficient to convert jewels into a set before iterating over stones?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Jewels and Stones from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Jewels and Stones drill