Jewels and Stones: Set Membership Counting
LeetCode 771. Jewels and Stones is one of the most popular easy problems, and for good reason. It is a clean, minimal example of how converting a string into a set unlocks fast membership checks. If you have solved Contains Duplicate, you already know the core idea. This problem just applies it in a slightly different way.
You are given a string jewels representing the types of stones that are jewels, and a string stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of your stones are also jewels. Letters are case sensitive.
Examples:
- jewels =
"aA", stones ="aAAbbbb"returns3 - jewels =
"z", stones ="ZZ"returns0
The approach
The brute force way is to loop through each stone and, for each one, scan the entire jewels string to see if it matches. That works, but it is O(j * s) where j is the length of jewels and s is the length of stones. You can do better.
The key insight is to convert the jewels string into a set first. A set gives you O(1) average-time lookups, so checking whether a stone is a jewel becomes a constant-time operation. Then you just iterate through the stones string once, counting every character that appears in the jewel set.
This is the same "build a lookup structure, then scan" pattern you see in dozens of hash map problems.
Visual walkthrough
Step 1: Build the jewel set from "aA"
Convert jewels string into a set: {'a', 'A'}. This gives O(1) lookups.
Step 2: Check stone 'a' at index 0
'a' is in the jewel set. Increment count to 1.
Step 3: Check stone 'A' at index 1
'A' is in the jewel set. Increment count to 2.
Step 4: Check stone 'A' at index 2
'A' is in the jewel set. Increment count to 3.
Step 5: Final result
Stones at indices 3 through 6 are 'b', which is not in the jewel set. The final count is 3.
Python solution
def numJewelsInStones(jewels, stones):
jewel_set = set(jewels)
return sum(1 for s in stones if s in jewel_set)
Line by line: first, you build a set from the jewels string. Python's set() constructor iterates through each character and adds it, giving you {'a', 'A'} for the input "aA". Then the generator expression walks through every character in stones, yields 1 each time the character is found in the set, and sum() adds them up. The result is the total count of stones that are jewels.
You could also check membership directly against the jewels string with if s in jewels, but that turns each lookup into an O(j) scan instead of O(1). For small inputs it does not matter, but using a set is the correct habit to build. It scales to any input size and signals to interviewers that you understand hash-based lookups.
Complexity analysis
Time: O(j + s) where j is the length of jewels and s is the length of stones. Building the set costs O(j), and scanning the stones costs O(s) with each lookup at O(1).
Space: O(j) for the jewel set. The set stores at most j characters.
| Aspect | Value |
|---|---|
| Time | O(j + s) |
| Space | O(j) |
| Difficulty | Easy |
Building blocks
Set membership
Converting a collection into a set for O(1) membership checks is one of the most common patterns in algorithm problems. You build the set once, then query it as many times as you need. This same idea powers Contains Duplicate, Happy Number, and many hash map pattern problems. The underlying data structure is a hash table, and the in operator on a Python set runs in O(1) average time.
lookup = set(collection)
if item in lookup:
# found
Generator expression counting
The sum(1 for ... if ...) pattern is a compact way to count items that satisfy a condition. It avoids building an intermediate list in memory. You can think of it as a filtered count: for every element that passes the condition, you contribute 1 to the total. This pattern is useful any time you need to count matches without storing them.
count = sum(1 for x in items if condition(x))
Edge cases
- All stones are jewels: every character in stones appears in the jewel set, so the count equals
len(stones). - No stones are jewels: no character in stones is in the jewel set, returning 0. The second example (
jewels = "z",stones = "ZZ") demonstrates this since case matters. - Empty jewels string: the jewel set is empty, so no stone can be a jewel. The count is always 0.
- Single-character strings: both jewels and stones have length 1. You just check if the one stone equals the one jewel.
From understanding to recall
This problem is simple to understand on a first read. The real value is in making the set-based lookup pattern automatic. When you encounter a harder problem that requires fast membership checks, you want the "convert to a set, then query" step to be something you reach for without thinking. Drilling this small problem with spaced repetition builds that reflex so it fires reliably under interview pressure.
Related posts
- Contains Duplicate - Same pattern of using a set for O(1) membership checks
- Valid Anagram - Character frequency comparison using hash maps
- First Unique Character in a String - Another string + hash map problem for character lookups