# Jewels and Stones (via Leetcode)

- March 25, 2020
- Key Terms: functions, loops

### Problem Statement¶

You're given strings `J`

representing the types of stones that are jewels, and `S`

representing the stones you have. Each character in `S`

is a type of stone you have. You want to know how many of the stones you have that are also jewels.

The letters in `J`

are guaranteed distinct, and all characters in `J`

and `S`

are letters. Letters are case sensitive, so `"a"`

is considered a different type of stone from `"A"`

.

### Test Cases¶

**Test case #1**:

- Input:
`J = "aA"`

,`S = "aAAbbbb"`

- Output:
`3`

- Reasonsing: The first 3 characters in
`S`

are characters that are in`J`

**Test case #2**:

- Input:
`J = "z"`

,`S = "ZZ"`

- Output:
`0`

- Reasonsing: There are no instances of
`z`

in`S`

```
# assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
# assert count_jewels_in_stones(J = "z", S = "ZZ") == 0
```

### Pseudocode¶

This code uses minimal storage - a low space complexity - of just O(1) since the 1 represents the space of the variable `count_jewels_in_collection`

.

However, this code has a high time complexity because for every element in `J`

, I must search all elements in `S`

. If we use the letter `n`

to assign the length of items in `J`

and `m`

to assign the length of items in `S`

, then the time complexity is O(mn).

```
# create function to take in J and S
# create a variable - a counter - to count the number of jewels found in the stones collection
# iterate over each element in J
# iterate over each item in S
# if element is equal to item
# increment the counter by 1
# return counter
```

### Code¶

```
def count_jewels_in_stones(J, S):
count_jewels_in_collection = 0
for element in J:
for item in S:
if element == item:
count_jewels_in_collection += 1
return count_jewels_in_collection
```

Let's run the `assert`

statements below to verify the function passes these test cases.

```
assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones(J = "z", S = "ZZ") == 0
```

### Pseudocode #2 Solution¶

The above answer had high time complexity and low space complexity. I can design an alternative solution as a tradeoff with low time complexity and high space complexity.

I will use a Python set covered in detail here in the official documentation.

In the code below, the set represents an O(n) space complexity and the variable is an O(1) space complexity.

I iterate over each element in `S`

so my code has an O(m) time complexity.

```
# assign each letter in J to be a value in a Python set
# store a variable as a counter of occurences of J in S
# iterate over each element in S
# if element is in Python set of S characters
# append 1 to counter
```

### Code #2 Solution¶

```
def count_jewels_in_stones2(J, S):
s_set = set(J)
count_jewels_in_collection = 0
for item in S:
if item in s_set:
count_jewels_in_collection += 1
return count_jewels_in_collection
```

Let's run the `assert`

statements below to verify this new function passes these test cases.

```
assert count_jewels_in_stones2(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones2(J = "z", S = "ZZ") == 0
```