We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Jewels and Stones

Number: 782

Difficulty: Easy

Paid? No

Companies: Microsoft, Google, Meta, Amazon, Apple, Yandex

Problem Description

Given two strings jewels and stones, count how many stones you have that are also jewels. Each character in stones represents a type of stone, and the letters in jewels indicate which stones are jewels. Note that letters are case sensitive.

Key Insights

  • Use a hash set to store the jewels for O(1) membership checking.
  • Iterate over every stone and check if it is in the jewels set.
  • Count and return the number of stones that are jewels.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of stones and m is the length of jewels. Space Complexity: O(m), for storing the jewels in a set.

Solution

The solution involves using a hash set data structure to store all the jewels so that each lookup during the iteration over stones is constant time. Then, iterate over each stone in the stones string; if the stone exists in the hash set, increment a counter. Finally, return the counter. This approach efficiently checks membership and solves the problem with linear time complexity relative to the input sizes.

Code Solutions

# Function to count the number of jewels in stones
def numJewelsInStones(jewels, stones):
    # Create a set from jewels for O(1) lookup
    jewels_set = set(jewels)
    # Initialize count of jewels
    count = 0
    # Iterate over each stone in stones
    for stone in stones:
        # If stone is in jewels_set, increment count
        if stone in jewels_set:
            count += 1
    return count

# Example usage:
print(numJewelsInStones("aA", "aAAbbbb"))  # Expected output: 3
← Back to All Questions