Jewels and Stones — HashSet Membership Lookup Done Right

Problem Statement#

You are 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".

Constraints:

• 1 <= jewels.length, stones.length <= 50
• jewels and stones consist of only English letters.
• All characters in jewels are unique.

Example 1:
Input:  jewels = "aA", stones = "aAAbbbb"
Output: 3
Explanation: 'a' is a jewel (count 1), 'A' is a jewel (count 2). Total: 3.

Example 2:
Input:  jewels = "z", stones = "ZZZ"
Output: 0
Explanation: 'z' != 'Z' — case-sensitive comparison. No jewels found.

Example 3:
Input:  jewels = "abc", stones = "aabbcc"
Output: 6
Explanation: All stones are jewels. Count = 2 + 2 + 2 = 6.

Why This Problem Matters#

Jewels and Stones is the simplest possible illustration of one of the most important performance patterns in software engineering: replacing a repeated linear search with an O(1) hash set lookup. The naive approach — for each stone, scan the entire jewels string to check membership — costs O(j * s) where j is the length of jewels and s is the length of stones. The optimized approach builds the jewels set once in O(j) and then performs each stone lookup in O(1).

Amazon uses this problem in phone screens because it directly mirrors real production patterns. Imagine checking whether each incoming request IP address is in a blocklist: you would never scan the entire blocklist for each request. You would load the blocklist into a hash set once and perform O(1) lookups. Jewels and Stones is that pattern in its purest form.

Despite the problem's simplicity, interviewers watch for several things: Do you immediately reach for a set (not a list or string) for the jewels? Do you explain the time complexity correctly? Do you mention that the problem guarantees all jewels characters are unique (which is why a set and the original string perform identically here — but a set generalizes better and communicates intent)?

The problem also demonstrates the value of data structure choice for readability. s in jewel_set clearly communicates "check if this stone is a jewel type." s in jewels_string works for the same reason (Python string membership is O(j)), but using a set communicates intent more clearly and generalizes to any case where the lookup list has duplicates or varies dynamically.

The Core Insight#

The problem asks: for each stone, is its type in the jewel types set? This is a repeated membership query. The key insight is that membership in an unordered collection of unique items should be answered in O(1) using a hash set, not O(n) by linear scan.

Build the jewel types into a hash set once. Then iterate over stones, checking each stone against the set. The total cost is O(j + s): O(j) to build the set and O(s) with O(1) per lookup.

The problem constraint says all jewel characters are unique, which means there is no frequency tracking needed — just membership. A set is the right data structure: it tracks presence, not count.

For a one-liner in Python: sum(s in set(jewels) for s in stones) — build the set once (Python's set constructor from a string is O(j)), then sum boolean membership results. The generator expression keeps memory low and the code expressive.

Visual Dry Run#

Input: jewels = "aA", stones = "aAAbbbb"

Step 1 — Build jewel set: jewel_set = {'a', 'A'}

Step 2 — Scan stones:

Return 3.

Solution (Optimal)#

def numJewelsInStones(jewels: str, stones: str) -> int:
    # Build O(1) lookup set from jewel types
    jewel_set = set(jewels)
 
    # Count stones that are jewels
    return sum(stone in jewel_set for stone in stones)
 
 
# Explicit loop version — same logic, more readable for beginners
def numJewelsInStones_explicit(jewels: str, stones: str) -> int:
    jewel_set = set(jewels)
    count = 0
    for stone in stones:
        if stone in jewel_set:
            count += 1
    return count

var numJewelsInStones = function(jewels, stones) {
    // Build O(1) lookup set from jewel types
    const jewelSet = new Set(jewels);
 
    // Count stones that are jewels
    let count = 0;
    for (const stone of stones) {
        if (jewelSet.has(stone)) count++;
    }
    return count;
};
 
 
// One-liner alternative using filter
var numJewelsInStones_oneliner = function(jewels, stones) {
    const jewelSet = new Set(jewels);
    return [...stones].filter(s => jewelSet.has(s)).length;
};

Complexity Analysis

For the constraints in this problem (max 50 characters each), the brute force is fast enough. But the hash set approach is conceptually correct and scales to arbitrarily large inputs.

Common Mistakes#

• Using in on a string instead of a set. In Python, stone in jewels works (string membership is O(j) in CPython), but this communicates "search the string" not "check the set." Use set(jewels) to make intent explicit and to generalize correctly. More importantly, in languages like JavaScript, jewels.includes(stone) is O(j) per stone, making the overall algorithm O(j * s) — building a Set is essential.
• Rebuilding the set inside the loop. sum(s in set(jewels) for s in stones) in Python actually rebuilds the set for each character in some implementations. Use a pre-built set variable to avoid O(j * s) work.
• Forgetting case sensitivity. 'a' and 'A' are different jewel types. Do not call .lower() or .upper() unless the problem explicitly says case-insensitive.
• Using a list instead of a set. list(jewels) maintains order and allows duplicates, but lookup is O(j) not O(1). Always prefer a set for membership queries.
• Using a frequency map when you only need a set. Since the problem only asks "is this stone a jewel type?" — not "how often does this stone appear in jewels?" — a set is the right data structure. A frequency map (Counter) adds unnecessary overhead.

Follow-up Questions#

What if the jewels string can contain duplicates (the uniqueness constraint is removed)? Use a set regardless — building a set from a string with duplicates still gives correct membership checking. The set naturally deduplicates.

What if you need to count distinct jewel types found (not total count)? Collect jewel-type stones into a set. Return the size of the intersection: len(set(stones) & set(jewels)).

What if the jewels and stones lists can be very large (millions of elements)? The hash set approach scales perfectly: O(j + s) regardless of size. The brute force O(j * s) would be catastrophic at that scale.

How would you handle streaming stones (processing one stone at a time)? Pre-build the jewel set from jewels. For each incoming stone, perform a single O(1) set lookup. This is ideal for streaming — no buffering required.

What if you need the count per jewel type (how many of each jewel type you have)? Use a frequency map (Counter) for stones, then sum the counts for all jewel types: sum(stone_freq[j] for j in jewels).

Key Takeaways#

• LC 771 Jewels and Stones is the canonical "build a set, query in O(1)" interview pattern.
• Naive nested-loop scan is O(j * s); using a hash set drops it to O(j + s) with O(j) extra space.
• Comparison is case-sensitive — never apply .lower() or .upper().
• Use Set (or set) over arrays/strings for membership checks because intent is clearer and lookup is truly O(1).
• The same pattern shows up in production blocklist checks, allow-list ACL lookups, and feature-flag membership.
• For follow-ups (count distinct types, frequency per type), upgrade from set to Counter/Map.
• This problem trains the habit of converting repeated linear searches into hash-based lookups — a foundational performance reflex.

Related Problems#

• LC 771 — Jewels and Stones: This problem.
• LC 1832 — Check if the Sentence Is Pangram: Check if all 26 letters appear in a string — same set membership pattern.
• LC 2215 — Find the Difference of Two Arrays: Return elements unique to each array — set difference operations.
• LC 349 — Intersection of Two Arrays: Return common elements — set intersection.
• LC 217 — Contains Duplicate: Check if any element appears more than once — set membership.
• LC 383 — Ransom Note: Frequency-based availability check — the next level of complexity above pure membership.