Domain 1EasyCORE

Jewels and Stones

The problem asks us to determine how many stones out of a given set are jewels. We are provided with two strings: `jewels` which contains the types of characters that are considered jewels, and `stones` which contains the collection of stones we have. The task is to count how many characters in `stones` are also present in `jewels`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

771. Jewels and Stones

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 87.0%


Problem Breakdown

The problem asks us to determine how many stones out of a given set are jewels. We are provided with two strings: jewels which contains the types of characters that are considered jewels, and stones which contains the collection of stones we have. The task is to count how many characters in stones are also present in jewels.

Inputs:

  • jewels: A string containing unique characters representing jewel types.
  • stones: A string containing characters representing the stones.

Outputs:

  • An integer representing the number of stones that are jewels.

Implicit Constraints:

  • The characters in jewels and stones are limited to English letters (both uppercase and lowercase).
  • The length of both strings is between 1 and 50.
  • All characters in jewels are unique.

Intuition

A brute-force approach would involve checking each stone against every jewel, resulting in a time complexity of O(n * m), where n is the length of stones and m is the length of jewels. This is inefficient given the constraints.

The key insight is to use a hash table (or set) to store the types of jewels. This allows for constant-time lookups, reducing the overall time complexity to O(n).

Approach

  1. Initialize a Set: Create a set from the jewels string. This will allow us to quickly check if a stone is a jewel.
  2. Count Jewels in Stones: Iterate through each character in the stones string and use the set to check if it is a jewel. If it is, increment a counter.
  3. Return the Count: After iterating through all stones, return the count of jewels.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the stones string. We iterate through each stone once and perform a constant-time lookup in the set.
  • Space Complexity: O(m), where m is the length of the jewels string. The space used by the set is proportional to the number of unique jewels.

Solution

def numJewelsInStones(jewels: str, stones: str) -> int:
    # Create a set of jewel characters for O(1) lookups
    jewel_set = set(jewels)
    
    # Count how many stones are also jewels
    count = 0
    for stone in stones:
        if stone in jewel_set:
            count += 1
    
    return count

Edge Cases Handled

  • Empty Strings: If either jewels or stones is empty, the function will correctly return 0 since there are no jewels to count.
  • All Characters Unique: Since all characters in jewels are unique by problem statement, the set creation and lookup operations remain efficient.
  • Case Sensitivity: The solution respects case sensitivity as it treats uppercase and lowercase letters distinctly.