Jewels and Stones

Difficulty: Easy | Acceptance: 89.50% | Paid: No Topics: Hash Table, String

You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of your stones are also jewels.

Letters are case sensitive, so “a” is considered a different type of stone from “A”.

• Examples
• Constraints
• Brute Force
• Hash Set
• Boolean Array

Examples

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints

1 <= jewels.length, stones.length <= 50
jewels and stones consist of only English letters.
All the characters of jewels are unique.

Brute Force

Intuition Iterate through each stone and check if it exists in the jewels string by scanning the jewels string.

Steps

• Initialize a counter to 0.
• Loop through each character in the stones string.
• For each stone, loop through each character in the jewels string.
• If a match is found, increment the counter and break the inner loop.
• Return the counter.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        count = 0
        for s in stones:
            for j in jewels:
                if s == j:
                    count += 1
                    break
        return count

Complexity

• Time: O(J * S), where J is the length of jewels and S is the length of stones.
• Space: O(1)
• Notes: Simple to implement but inefficient for large inputs.

Hash Set

Intuition Store the unique jewel characters in a hash set for O(1) average time complexity lookups.

Steps

• Create a set from the jewels string.
• Initialize a counter to 0.
• Iterate through each character in the stones string.
• If the character exists in the set, increment the counter.
• Return the counter.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        return sum(1 for s in stones if s in jewel_set)

Complexity

• Time: O(J + S)
• Space: O(J)
• Notes: Optimizes lookup time at the cost of O(J) space.

Boolean Array

Intuition Since the input consists only of English letters (52 unique characters case-sensitive), we can use a fixed-size boolean array for faster lookups than a hash set and with lower overhead.

Steps

• Create a boolean array of size 128 (covering standard ASCII) or 256.
• Iterate through jewels and mark the corresponding index in the array as true.
• Iterate through stones. If the character’s index in the array is true, increment the counter.
• Return the counter.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        seen = [False] * 128
        for j in jewels:
            seen[ord(j)] = True
        return sum(1 for s in stones if seen[ord(s)])

Complexity

• Time: O(J + S)
• Space: O(1)
• Notes: Very efficient due to direct memory access and fixed size.