Jewels and Stones
Jewels and Stones: given a string of jewel types and a string of stones you own, count how many of your stones are jewels. Letters are case-sensitive, so a and A are different types.
- 1 <= jewels.length, stones.length <= 50
- jewels and stones consist of only English letters
- All the characters of jewels are unique
Intuition
Every stone needs one question answered — is this character a jewel? — and the answer never changes during the scan. Storing the jewel types in a hash set turns that question into an O(1) lookup, so counting the stones costs one pass. The nested-loop version asks the same question by re-scanning the jewel string every time, which is pure repeated work a set eliminates.
When one input is consulted repeatedly and the other is traversed once, load the first into a set or map before touching the second. The signal is an inner loop whose result depends only on the current outer element. Contains Duplicate and Intersection of Two Arrays share this shape.
Approach
Before reading on: decide which of the two strings should be preprocessed and why. Then work out the running time of the version that loops over jewels inside the loop over stones, and what the set saves.
Separate the fixed reference from the stream
The two strings play different roles. jewels is a fixed reference set, consulted many times and never changed. stones is a stream, visited once. That asymmetry is the whole design: preprocess the thing you consult repeatedly, and stream the thing you visit once. Loading jewels into a set costs O(j) up front and makes every subsequent membership test constant time, which is exactly the trade a hash set exists to make.
Why a set beats the nested scan
The naive solution loops over stones and, for each, loops over jewels looking for a match, costing O(j · s). With a set the inner loop disappears and the total drops to O(j + s). On the constraint limits — both strings up to 50 characters — the difference is invisible, but the reasoning is what generalises: the naive version repeats an identical search up to fifty times per stone, and the set answers each in one probe by hashing the character directly to its bucket.
Case sensitivity is a specification detail, not an accident
The problem states that letters are case-sensitive and that a is considered different from A. Because a hash set on characters compares exact code points, this behaviour comes for free — no normalisation, no lower(). The bug to avoid is adding case-insensitivity by folding case out of habit, which would count A stones against an a jewel and inflate the answer. Time O(j + s), space O(j) bounded by the alphabet.
Solution & live demo
Common pitfalls
Re-scanning the jewels string per stone
for stone in stones:
for j in jewels:
if stone == j:
count += 1jewel_set = set(jewels)
for stone in stones:
if stone in jewel_set:
count += 1The inner loop repeats an identical search for every stone, giving O(j · s). The set answers the same question in one hash probe, and the lookup cost stops depending on how many jewel types there are.
Normalising case
if stone.lower() in jewels.lower():
if stone in jewel_set:
The problem explicitly treats 'a' and 'A' as different types. Folding case makes 'A' stones match an 'a' jewel, overcounting on any mixed-case input.
Counting jewel types rather than stones
for j in jewels:
if j in stones:
count += 1for stone in stones:
if stone in jewel_set:
count += 1This counts how many jewel types appear at least once, not how many stones you hold. For jewels 'a' and stones 'aaa' it returns 1 instead of 3.
Edge cases
The loop never runs and the count stays 0.
The set is empty, every membership test fails, and 0 is returned.
Both cases are jewel types, so all three matching stones count.
The count equals the length of the stones string.
The set deduplicates them, which changes nothing about the count.