LeetCode 771 - Jewels and Stones

In this problem, we are given two strings, jewels and stones. The string jewels represents all stone types that are considered jewels. Each character is a unique jewel type. For example, if jewels = "aA", then both lowercase 'a' and uppercase 'A' are jewel types.

leetcodeeasyhash-tablestring

LeetCode Problem 771

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

In this problem, we are given two strings, jewels and stones.

The string jewels represents all stone types that are considered jewels. Each character is a unique jewel type. For example, if jewels = "aA", then both lowercase 'a' and uppercase 'A' are jewel types.

The string stones represents all stones we currently own. Every character in this string corresponds to one stone. Our task is to count how many stones in stones are also present in jewels.

The comparison is case sensitive. This is extremely important. The character 'a' is different from 'A', so they must be treated as separate stone types.

The expected output is a single integer representing the number of stones that are jewels.

For example:

  • jewels = "aA"
  • stones = "aAAbbbb"

The stones are:

  • 'a' -> jewel
  • 'A' -> jewel
  • 'A' -> jewel
  • 'b' -> not jewel
  • 'b' -> not jewel
  • 'b' -> not jewel
  • 'b' -> not jewel

So the answer is 3.

The constraints are very small:

  • 1 <= jewels.length, stones.length <= 50
  • Only English letters are used
  • All characters in jewels are unique

Because the input size is tiny, even a brute-force solution would work efficiently enough. However, this problem is designed to introduce the idea of using a hash-based lookup structure for faster membership checks.

Some important edge cases include:

  • No stones are jewels
  • Every stone is a jewel
  • Mixed uppercase and lowercase letters
  • A single-character input
  • Repeated jewel stones in stones

The problem guarantees that jewels contains unique characters, which simplifies lookup logic because we never need to handle duplicate jewel definitions.

Approaches

Brute Force Approach

The most straightforward solution is to compare every stone against every jewel.

For each character in stones, we iterate through all characters in jewels and check whether they match. If a match is found, we increment our answer counter.

This works because every stone is explicitly checked against every possible jewel type, guaranteeing correctness.

However, this approach performs unnecessary repeated comparisons. If there are n stones and m jewel types, the total number of comparisons becomes O(n * m).

Even though the constraints are small enough that this passes comfortably, it is not the most efficient way to solve the problem.

Optimal Approach

The key observation is that we repeatedly ask the same question:

"Is this stone type a jewel?"

This is a classic membership lookup problem, which is exactly what a hash set is designed for.

We can place all jewel characters into a set. Then, for every stone in stones, we simply check whether it exists in the set.

A hash set provides average-case O(1) lookup time, so the entire solution becomes linear with respect to the input size.

This improves the overall complexity from O(n * m) to O(n + m).

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Compare every stone with every jewel
Optimal O(n + m) O(m) Use a hash set for constant-time membership lookup

Here:

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

Algorithm Walkthrough

Optimal Algorithm

  1. Create a hash set containing all characters from jewels.

This allows us to quickly determine whether a stone type is a jewel. Hash sets are ideal because membership checks are very fast on average. 2. Initialize a counter variable to 0.

This variable will store the number of jewel stones found in stones. 3. Iterate through each character in stones.

Each character represents one stone we own. 4. For each stone, check whether it exists in the jewel set.

If the stone character is present in the set, it means that stone is a jewel. 5. If the stone is a jewel, increment the counter.

We count every occurrence separately because repeated stones are distinct stones. 6. After processing all stones, return the counter.

This final count represents the total number of jewel stones.

Why it works

The algorithm works because the set contains exactly the valid jewel types. Every stone is checked exactly once against this set. If the stone exists in the set, it contributes to the answer. Since all stones are processed and every jewel membership check is accurate, the final counter is guaranteed to equal the total number of jewel stones.

Python Solution

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

        jewel_count = 0

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

        return jewel_count

The implementation begins by converting jewels into a set. In Python, set membership checks are highly efficient, making this the ideal structure for repeated lookups.

The variable jewel_count keeps track of how many jewel stones we have encountered.

We then iterate through every character in stones. For each stone, we check whether it exists in jewel_set. If it does, we increment the counter.

Finally, after all stones have been processed, the method returns the total count.

The implementation directly follows the algorithm described earlier and maintains clear readability.

Go Solution

func numJewelsInStones(jewels string, stones string) int {
    jewelSet := make(map[rune]bool)

    for _, jewel := range jewels {
        jewelSet[jewel] = true
    }

    count := 0

    for _, stone := range stones {
        if jewelSet[stone] {
            count++
        }
    }

    return count
}

In Go, there is no built-in set type, so we simulate a set using a map[rune]bool.

Each jewel character is inserted into the map with the value true. Then we iterate through stones and check whether each stone exists in the map.

The Go implementation uses rune iteration instead of byte indexing. While this problem only contains English letters, iterating over runes is generally safer and more idiomatic for strings in Go.

There are no concerns about integer overflow because the maximum possible answer is only 50.

Worked Examples

Example 1

Input:

jewels = "aA"
stones = "aAAbbbb"

First, create the jewel set:

{'a', 'A'}

Now iterate through stones.

Stone In Jewel Set? Count
a Yes 1
A Yes 2
A Yes 3
b No 3
b No 3
b No 3
b No 3

Final answer:

3

Example 2

Input:

jewels = "z"
stones = "ZZ"

Create the jewel set:

{'z'}

Now process each stone.

Stone In Jewel Set? Count
Z No 0
Z No 0

Final answer:

0

This example highlights the importance of case sensitivity. Lowercase 'z' and uppercase 'Z' are different characters.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Building the set takes O(m), scanning stones takes O(n)
Space O(m) The hash set stores all jewel types

The algorithm processes each jewel once while building the set and each stone once while counting matches. Since hash set lookups are constant time on average, the total runtime is linear.

The additional memory usage comes entirely from storing the jewel characters in the set.

Test Cases

solution = Solution()

assert solution.numJewelsInStones("aA", "aAAbbbb") == 3  # basic mixed case example
assert solution.numJewelsInStones("z", "ZZ") == 0  # case sensitivity check
assert solution.numJewelsInStones("a", "a") == 1  # single matching character
assert solution.numJewelsInStones("a", "b") == 0  # single non-matching character
assert solution.numJewelsInStones("abc", "abcabc") == 6  # all stones are jewels
assert solution.numJewelsInStones("abc", "def") == 0  # no stones are jewels
assert solution.numJewelsInStones("A", "AAAAA") == 5  # repeated jewel stones
assert solution.numJewelsInStones("aA", "AaAa") == 4  # alternating uppercase and lowercase
assert solution.numJewelsInStones("xyz", "xXyYzZ") == 3  # mixed matching and non-matching
assert solution.numJewelsInStones("m", "mmmmmmmmmm") == 10  # repeated single jewel
Test Why
"aA", "aAAbbbb" Validates the primary example
"z", "ZZ" Verifies case sensitivity
"a", "a" Smallest matching input
"a", "b" Smallest non-matching input
"abc", "abcabc" Every stone is a jewel
"abc", "def" No jewel stones exist
"A", "AAAAA" Repeated jewel occurrences
"aA", "AaAa" Mixed uppercase and lowercase matching
"xyz", "xXyYzZ" Partial matching with case differences
"m", "mmmmmmmmmm" Stress repeated counting logic

Edge Cases

One important edge case is case sensitivity. Many incorrect solutions accidentally treat uppercase and lowercase letters as equivalent. For example, 'a' and 'A' must be treated as different stone types. The implementation handles this correctly because character comparisons in both Python and Go are naturally case sensitive.

Another important edge case is when none of the stones are jewels. In this scenario, the counter should remain 0 throughout execution. Since the algorithm only increments the counter when membership exists in the set, the implementation naturally handles this case correctly.

A third important edge case occurs when every stone is a jewel. In this case, the counter increases on every iteration through stones. The implementation correctly counts all occurrences independently, including duplicates.

A fourth subtle edge case involves repeated jewel stones inside stones. For example, if jewels = "a" and stones = "aaaaa", the answer should be 5, not 1. The algorithm processes every stone individually and increments the count for each matching occurrence, ensuring duplicates are counted properly.