# LeetCode 771: Jewels and Stones

## Problem Restatement

We are given two strings:

```python
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

| Item | Meaning |
|---|---|
| Input | `jewels`, the jewel types |
| Input | `stones`, the stones we have |
| Output | Number of stones whose type appears in `jewels` |
| Case sensitivity | `"a"` and `"A"` are different |

Example function shape:

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

## Examples

Example 1:

```python
jewels = "aA"
stones = "aAAbbbb"
```

Output:

```python
3
```

The jewel types are:

```text
a
A
```

The stones are:

```text
a A A b b b b
```

There are three stones that are jewels:

```text
a, A, A
```

So the answer is `3`.

Example 2:

```python
jewels = "z"
stones = "ZZ"
```

Output:

```python
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`.

```python
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:

```python
jewel_set = set(jewels)
```

Now checking:

```python
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Build the set once, then scan all stones once |
| Space | `O(m)` | The set stores jewel types |

## Implementation

```python
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:

```python
jewel_set = set(jewels)
```

For example:

```python
jewels = "aA"
```

becomes:

```python
{"a", "A"}
```

Then we count stones that appear in this set:

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

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

Finally:

```python
return answer
```

returns the total number of jewel stones.

## Compact Python Version

The same logic can be written more compactly:

```python
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

```python
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:

| Test | Why |
|---|---|
| `"aA", "aAAbbbb"` | Main example with mixed case |
| `"z", "ZZ"` | Confirms case sensitivity |
| `"abc", "abcdef"` | Some stones are jewels |
| `"A", "aA"` | Uppercase and lowercase differ |
| `"xY", "xxYYYz"` | Counts repeated jewel stones |