Problem Description

You are given two strings: jewels and stones.

The string jewels represents the types of stones that are considered jewels. Each character in this string represents a unique type of jewel.

The string stones represents all the stones you have. Each character in this string represents one stone.

Your task is to count how many of your stones are also jewels. In other words, you need to find how many characters in stones also appear in jewels.

An important detail is that letters are case-sensitive. This means "a" and "A" are treated as completely different types of stones.

For example:

• If jewels = "aA" and stones = "aAAbbbb", the answer would be 3 because you have three stones ("a", "A", "A") that match the jewel types defined in jewels.
• The character "a" appears once in stones and is a jewel
• The character "A" appears twice in stones and is a jewel
• The character "b" appears four times in stones but is not a jewel

The solution uses a set to store all jewel types for O(1) lookup time, then iterates through each stone to check if it's a jewel, counting the matches.

Intuition

The core insight here is recognizing that this is fundamentally a membership checking problem. We need to repeatedly ask: "Is this stone a jewel?" for every stone we have.

When we need to check membership multiple times, a hash set immediately comes to mind because it provides O(1) lookup time. If we were to check each stone against the jewels string directly using something like stone in jewels, we'd be doing a linear search for each stone, resulting in O(n*m) time complexity where n is the length of stones and m is the length of jewels.

By converting jewels to a set first, we transform the problem:

• Build a set of all jewel types: s = set(jewels) - This takes O(m) time
• For each stone, check if it exists in our jewel set: c in s - Each check is O(1)
• Count all the stones that are jewels

The beauty of the solution sum(c in s for c in stones) is that it leverages Python's generator expression with the sum() function. The expression c in s evaluates to True (which equals 1) when the stone is a jewel, and False (which equals 0) when it's not. Summing these boolean values gives us the total count directly.

This approach scales well because no matter how many jewel types we have, checking if a stone is a jewel remains a constant-time operation thanks to the hash set's properties.

Solution Approach

The solution uses a Hash Table (implemented as a Python set) to efficiently count jewels among the stones.

Step-by-step implementation:

1. Create a hash set of jewels:

   s = set(jewels)

   This converts the jewels string into a set, where each character becomes a unique element. For example, if jewels = "aA", then s = {'a', 'A'}. This preprocessing step takes O(m) time where m is the length of jewels.

2. Count stones that are jewels:

   return sum(c in s for c in stones)

   This line does several things:

   • for c in stones: Iterates through each character (stone) in the stones string
   • c in s: Checks if the current stone c exists in our jewel set s. This returns True or False
   • The generator expression (c in s for c in stones) produces a sequence of boolean values
   • sum(): Adds up all the boolean values, where True counts as 1 and False counts as 0

Why use a set instead of the original string?

Checking membership in a set is O(1) on average, while checking membership in a string is O(m). Since we need to perform this check for every stone, using a set reduces our overall time complexity from O(n*m) to O(n+m).

Time Complexity: O(n + m), where n is the length of stones and m is the length of jewels

• O(m) to build the set
• O(n) to iterate through all stones with O(1) lookup for each

Space Complexity: O(m) for storing the jewel types in the set

Example Walkthrough

Let's walk through a concrete example with jewels = "aA" and stones = "aAAbbbb".

Step 1: Create a hash set of jewels

• We convert jewels = "aA" into a set
• s = set("aA") results in s = {'a', 'A'}
• Now we have O(1) lookup for any jewel type

Step 2: Iterate through each stone and check if it's a jewel

Let's trace through each character in stones = "aAAbbbb":

Step 3: Sum the results

• The generator expression (c in s for c in stones) produces: True, True, True, False, False, False, False
• When passed to sum(), these boolean values are treated as: 1, 1, 1, 0, 0, 0, 0
• Final sum: 1 + 1 + 1 + 0 + 0 + 0 + 0 = 3

Therefore, we have 3 stones that are jewels.

The complete solution in one line: return sum(c in set(jewels) for c in stones)

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the length of the string jewels and n is the length of the string stones. This breaks down as:

• Creating the set from jewels takes O(m) time
• Iterating through each character in stones takes O(n) time
• The membership check c in s for a set is O(1) on average
• Therefore, the total time complexity is O(m) + O(n) = O(m + n)

The space complexity is O(m) or alternatively O(|Σ|), where |Σ| represents the size of the character set. The analysis is:

• The set s stores at most m unique characters from jewels, requiring O(m) space
• Since the problem constrains the input to uppercase and lowercase English letters, the set can contain at most 52 distinct characters, making the space complexity bounded by O(|Σ|) where |Σ| = 52
• The generator expression sum(c in s for c in stones) uses O(1) additional space
• Therefore, the space complexity is O(min(m, |Σ|)), which simplifies to O(|Σ|) in the worst case

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting Case Sensitivity

A frequent mistake is assuming that jewels and stones are case-insensitive, leading to incorrect counts.

Incorrect approach:

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    # Wrong: Converting to lowercase loses case distinction
    jewel_set = set(jewels.lower())
    return sum(char.lower() in jewel_set for char in stones)

Why it's wrong: If jewels = "aA" and stones = "aAAbbbb", this would incorrectly count all three A's and the single 'a' as the same type, potentially giving wrong results when the problem explicitly states that 'a' and 'A' are different jewel types.

Correct approach: Keep the original case as shown in the provided solution.

2. Using String Membership Instead of Set

While functionally correct, using the string directly for membership checking is inefficient.

Inefficient approach:

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    # Works but inefficient: O(n*m) time complexity
    return sum(char in jewels for char in stones)

Why it's inefficient: Checking if a character exists in a string requires scanning through the string (O(m) operation). Doing this for each stone results in O(n*m) complexity instead of the optimal O(n+m).

3. Assuming Unique Characters in Jewels

While the problem states each character in jewels represents a unique type, some might write unnecessary code to handle duplicates.

Overcomplicated approach:

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    # Unnecessary: set() already handles duplicates
    jewel_set = set()
    for jewel in jewels:
        if jewel not in jewel_set:
            jewel_set.add(jewel)
    return sum(char in jewel_set for char in stones)

Why it's unnecessary: The set() constructor automatically handles duplicates, making the manual checking redundant. Even if jewels had duplicates (though the problem says it won't), set(jewels) would handle it correctly.