# Jewels and Stones
**Difficulty:** EASY
[External](https://leetcode.com/problems/jewels-and-stones)
Canonical: https://scaleengineer.com/dsa/problems/jewels-and-stones
**Data structures:** Hash Table, String
---
## Problem
You're 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"`.

**Example 1:**

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

**Example 2:**

**Input:** jewels = "z", stones = "ZZ"
**Output:** 0

**Constraints:**

* `1 <= jewels.length, stones.length <= 50`
* `jewels` and `stones` consist of only English letters.
* All the characters of `jewels` are **unique**.

# Approaches
## Brute Force with Nested Loops
This is a straightforward brute-force approach where we compare every stone against every jewel. We iterate through each character in the `stones` string, and for each stone, we perform another full iteration through the `jewels` string to check for a match.
**Time:** O(S * J) - Where S is the length of `stones` and J is the length of `jewels`. For each of the S stones, we might have to iterate through all J jewels in the worst case. · **Space:** O(1) - We only use a few variables to store the count and loop indices, which does not depend on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space (O(1) space complexity).
**Cons:** Inefficient for large input strings due to its quadratic time complexity.; Performs many redundant comparisons if the `jewels` string is long.
### Explanation
In this method, we use two nested loops. The outer loop iterates over each stone you have, and the inner loop iterates over each type of jewel. For each stone, we check if it matches any of the jewel types. If a match is found, we increment a counter. Since the problem states that all jewel types are unique, we can add a small optimization: once a stone is identified as a jewel, we can stop searching for that particular stone and move on to the next one by breaking the inner loop. Despite this optimization, the fundamental approach remains a pairwise comparison of all stones against all jewels.

```java
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int jewelCount = 0;
        for (int i = 0; i < stones.length(); i++) {
            char stoneChar = stones.charAt(i);
            for (int j = 0; j < jewels.length(); j++) {
                char jewelChar = jewels.charAt(j);
                if (stoneChar == jewelChar) {
                    jewelCount++;
                    break; // Jewel types are unique, so we can move to the next stone.
                }
            }
        }
        return jewelCount;
    }
}
```
### Algorithm
- Initialize a counter `jewelCount` to 0.
- Iterate through each character `stoneChar` in the `stones` string.
- For each `stoneChar`, start a nested loop to iterate through each character `jewelChar` in the `jewels` string.
- If `stoneChar` is equal to `jewelChar`, increment `jewelCount` and break the inner loop.
- After iterating through all stones, return `jewelCount`.

## Using a Hash Set
A more efficient approach is to use a data structure that provides fast lookups. We can first store all the jewel types in a Hash Set. This allows us to check if a stone is a jewel in constant time on average. We iterate through the jewels once to build the set, and then iterate through the stones once to count the matches.
**Time:** O(J + S) - Where J is the length of `jewels` and S is the length of `stones`. It takes O(J) time to build the set and O(S) time to iterate through the stones. · **Space:** O(J) - Where J is the length of `jewels`. We need to store each unique jewel type in the hash set.
**Pros:** Significantly faster than the brute-force approach with linear time complexity.; A general-purpose solution that works well for any character set, not just English letters.
**Cons:** Uses extra space proportional to the number of jewel types.; Has a slight overhead due to hash computation and potential hash collisions, though minimal in practice.
### Explanation
The bottleneck in the brute-force approach is the repeated linear scan of the `jewels` string. We can eliminate this by pre-processing the jewels. We create a `HashSet` and populate it with all the characters from the `jewels` string. Building this set takes time proportional to the number of jewel types. After the set is built, we can iterate through the `stones` string. For each stone, we perform a lookup in the hash set. The `contains()` operation in a hash set is very fast, taking O(1) time on average. This reduces the overall time complexity from quadratic to linear.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> jewelSet = new HashSet<>();
        for (char j : jewels.toCharArray()) {
            jewelSet.add(j);
        }

        int jewelCount = 0;
        for (char s : stones.toCharArray()) {
            if (jewelSet.contains(s)) {
                jewelCount++;
            }
        }
        return jewelCount;
    }
}
```
### Algorithm
- Create an empty `HashSet<Character>` named `jewelSet`.
- Iterate through the `jewels` string and add each character to the `jewelSet`.
- Initialize a counter `jewelCount` to 0.
- Iterate through the `stones` string.
- For each character `stoneChar`, check if it is present in the `jewelSet` using the `contains()` method.
- If it is present, increment `jewelCount`.
- Return `jewelCount`.

## Optimized Lookup with a Boolean Array
This is the most optimized approach, building upon the hash set idea. Since the problem specifies that the characters are English letters, we can use a simple boolean array as a direct-access table instead of a hash set. This provides the same O(1) lookup time but with better performance due to no hashing overhead and constant space usage.
**Time:** O(J + S) - Where J is the length of `jewels` and S is the length of `stones`. It takes O(J) to populate the array and O(S) to check the stones. · **Space:** O(1) - The space required for the boolean array is constant (e.g., 128 booleans) and does not scale with the size of the input strings.
**Pros:** Extremely efficient with linear time complexity.; Constant space complexity, as the array size does not depend on the input length.; Typically faster in practice than a hash set due to direct memory access without hashing overhead.
**Cons:** This approach is specialized for a known, small character set (like ASCII). It is less flexible than a hash set if the character set were large or unknown (e.g., full Unicode).
### Explanation
We can leverage the fact that characters have underlying integer representations (ASCII values). We can create a boolean array, say of size 128, which is large enough to cover all uppercase and lowercase English letters. This array will act as a direct map where the index corresponds to a character's ASCII value. First, we iterate through the `jewels` string and mark the corresponding indices in our boolean array as `true`. This populates our 'set' of jewels. Then, we iterate through the `stones` string. For each stone, we check our boolean array at the index corresponding to the stone's character. If the value is `true`, we increment our count. This array lookup is an O(1) operation, and since the array size is fixed regardless of input size, the space complexity is constant.

```java
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        // 'z' has ASCII value 122. An array of size 128 is sufficient.
        boolean[] isJewel = new boolean[128];
        for (char j : jewels.toCharArray()) {
            isJewel[j] = true;
        }

        int jewelCount = 0;
        for (char s : stones.toCharArray()) {
            if (isJewel[s]) {
                jewelCount++;
            }
        }
        return jewelCount;
    }
}
```
### Algorithm
- Create a boolean array `isJewel` of size 128 (to cover ASCII values of English letters) and initialize all elements to `false`.
- Iterate through the `jewels` string. For each character `j`, set `isJewel[j] = true`.
- Initialize a counter `jewelCount` to 0.
- Iterate through the `stones` string.
- For each character `s`, check if `isJewel[s]` is `true`.
- If it is, increment `jewelCount`.
- Return `jewelCount`.

# Solutions
### Java

```java
class Solution { public int numJewelsInStones ( String jewels , String stones ) { int [] s = new int [ 128 ]; for ( char c : jewels . toCharArray ()) { s [ c ] = 1 ; } int ans = 0 ; for ( char c : stones . toCharArray ()) { ans += s [ c ]; } return ans ; } }
```

### JavaScript

```javascript
/** * @param {string} jewels * @param {string} stones * @return {number} */ var numJewelsInStones =
  function (jewels, stones) {
    const s = new Set(jewels.split(""));
    return stones.split("").reduce((prev, val) => prev + s.has(val), 0);
  };

```

### CPP

```cpp
class Solution { public: int numJewelsInStones ( string jewels , string stones ) { int s [ 128 ] = { 0 }; for ( char c : jewels ) s [ c ] = 1 ; int ans = 0 ; for ( char c : stones ) ans += s [ c ]; return ans ; } };
```

### Python

```python
class Solution : def numJewelsInStones ( self , jewels : str , stones : str ) -> int : s = set ( jewels ) return sum ( c in s for c in stones )
```