LeetCode 771: Jewels and Stones

Problem Restatement

We are given two strings:

jewels
stones

Each character in jewels represents a type of stone that is a jewel.

Each character in stones represents one stone we have.

We need to count how many stones are also jewels.

Letters are case-sensitive, so "a" and "A" are different stone types. The official statement also says all characters in jewels are unique.

Input and Output

Example function shape:

def numJewelsInStones(jewels: str, stones: str) -> int:
    ...

Examples

Example 1:

jewels = "aA"
stones = "aAAbbbb"

Output:

3

The jewel types are:

a
A

The stones are:

a A A b b b b

There are three stones that are jewels:

a, A, A

So the answer is 3.

Example 2:

jewels = "z"
stones = "ZZ"

Output:

0

The jewel type is lowercase "z".

The stones are uppercase "Z".

Since the comparison is case-sensitive, none of the stones are jewels.

First Thought: Check Each Stone Against jewels

A direct solution is to scan every stone and check whether it appears in jewels.

answer = 0

for stone in stones:
    if stone in jewels:
        answer += 1

This works.

But membership checking in a string may scan through the string.

So if jewels is longer, we repeat the same search many times.

Key Insight

We only need to know whether a stone type is a jewel.

That is a membership question.

A set is the right data structure:

jewel_set = set(jewels)

Now checking:

stone in jewel_set

is expected O(1) time.

Then we scan stones once and count matches.

Algorithm

1. Convert jewels into a set.
2. Initialize answer = 0.
3. For each character stone in stones:
   1. If stone is in the set, increment answer.
4. Return answer.

Correctness

The set jewel_set contains exactly the characters from jewels.

For each character in stones, the algorithm checks whether that character appears in jewel_set.

If it does, then this stone is one of the jewel types, so the algorithm counts it.

If it does not, then this stone is not a jewel, so the algorithm correctly ignores it.

Since every stone is checked exactly once, the final count is exactly the number of stones that are jewels.

Complexity

Let:

m = len(jewels)
n = len(stones)

Implementation

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        answer = 0

        for stone in stones:
            if stone in jewel_set:
                answer += 1

        return answer

Code Explanation

We first create a set of jewel types:

jewel_set = set(jewels)

For example:

jewels = "aA"

becomes:

{"a", "A"}

Then we count stones that appear in this set:

for stone in stones:
    if stone in jewel_set:
        answer += 1

Because the comparison is case-sensitive, "a" and "A" remain separate characters.

Finally:

return answer

returns the total number of jewel stones.

Compact Python Version

The same logic can be written more compactly:

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        return sum(stone in jewel_set for stone in stones)

In Python, True counts as 1 and False counts as 0, so the sum counts how many membership checks are true.

Testing

def run_tests():
    s = Solution()

    assert s.numJewelsInStones("aA", "aAAbbbb") == 3
    assert s.numJewelsInStones("z", "ZZ") == 0
    assert s.numJewelsInStones("abc", "abcdef") == 3
    assert s.numJewelsInStones("A", "aA") == 1
    assert s.numJewelsInStones("xY", "xxYYYz") == 5

    print("all tests passed")

run_tests()

Test meaning: