Problem statement

You are given jewels, a string where each character is a type of stone that counts as a jewel, and stones, a string where each character is a stone you have.

Return how many of your stones are jewels. Letters are case-sensitive, so "a" and "A" are different types.

Example 1

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

Example 2

Input: jewels = "z", stones = "ZZ"
Output: 0
Explanation: Case matters.

Example 3

Input: jewels = "abc", stones = "cba"
Output: 3

Constraints

• 1 <= jewels.length, stones.length <= 40
• All characters are English letters.
• The characters of jewels are distinct.

Hints for Jewels and Stones

1. Hint 1

   Put the jewel types into a hash set so each stone is a constant-time lookup.

2. Hint 2

   Then scan the stones once and count the hits.

How to solve Jewels and Stones

Put the jewel types in a hash set, then count stones whose type is in the set.

Approach

1. Build a set from jewels.
2. Count the characters of stones present in the set.

Why it works

Set membership is O(1), so each stone costs constant time instead of a scan over jewels.

Complexity

• Time — O(j + s)
• Space — O(j)

Pitfalls

• Case matters — a and A are different stones.

Reference solution

Python

def numJewelsInStones(jewels: str, stones: str) -> int:
    jewel_set = set(jewels)
    return sum(1 for ch in stones if ch in jewel_set)

Java

public static int numJewelsInStones(String jewels, String stones) {
    Set<Character> set = new HashSet<>();
    for (int i = 0; i < jewels.length(); i++) set.add(jewels.charAt(i));
    int count = 0;
    for (int i = 0; i < stones.length(); i++) {
        if (set.contains(stones.charAt(i))) count++;
    }
    return count;
}

C++

int numJewelsInStones(string jewels, string stones) {
    bool isJewel[128] = {false};
    for (char c : jewels) isJewel[(int) c] = true;
    int count = 0;
    for (char c : stones) {
        if (isJewel[(int) c]) count++;
    }
    return count;
}

JavaScript

var numJewelsInStones = function(jewels, stones) {
    const set = new Set(jewels.split(""));
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (set.has(stones[i])) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy