#771

Easy

LeetCode Problem Workspace

Jewels and Stones

Given two strings, determine how many of the stones you have are also jewels, considering case sensitivity.

Problem Statement

You are given two strings: jewels and stones. The jewels string contains the types of stones that are considered jewels, and the stones string contains the stones you possess. The task is to determine how many of the stones in the stones string are also jewels from the jewels string.

Letters in the strings are case-sensitive, meaning 'a' and 'A' represent different types of stones. For example, the string jewels = "aA" and stones = "aAAbbbb" would result in 3 jewels being found among the stones, as there are 3 'a' or 'A' characters in the stones string.

Examples

Example 1

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

Output: 3

Example details omitted.

Example 2

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

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Use a Hash Set for Jewels

Since jewels consist of unique characters, a hash set is an efficient data structure for storing them. This allows for constant time look-up when checking if a stone is a jewel.

Iterate Through Stones

For each character in the stones string, check if it exists in the jewels hash set. This step is linear in time complexity, and each check is constant time due to the hash set.

Count the Matches

For each stone that matches a jewel, increment the count. The final count will give the number of jewels found in the stones.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N) where N is the length of the stones string, due to the iteration over stones. Space complexity is O(M) where M is the number of unique jewels, as we use a hash set to store jewels.

What Interviewers Usually Probe

Look for candidates who can efficiently use hash tables for set membership checks.
Watch for candidates who consider edge cases like empty strings or case sensitivity.
Evaluate how quickly the candidate identifies the need for a hash set given the unique character constraint.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution with unnecessary data structures instead of using a hash set for jewels.
Failing to account for case sensitivity when checking if a stone is a jewel.
Ignoring edge cases like when there are no jewels or no stones.

Follow-up variants

If the jewels string contains repeated characters, candidates must adjust the approach accordingly.
The problem can be adjusted to handle larger input sizes, testing the solution's scalability.
The problem could be expanded by requiring the return of the list of jewel stones rather than just the count.

FAQ

What is the optimal time complexity for this problem?

The optimal time complexity is O(N), where N is the length of the stones string, as each stone is checked exactly once.

How do we handle case sensitivity in this problem?

Case sensitivity is handled by treating uppercase and lowercase letters as different characters. For example, 'a' and 'A' are distinct.

What data structure should we use for storing jewels?

A hash set is ideal for storing jewels because it allows O(1) average time complexity for membership checks.

How do we count how many stones are jewels?

We iterate through the stones string and check if each stone is present in the jewels hash set, incrementing the count each time.

What if the stones string is empty?

If the stones string is empty, the output will be 0 since there are no stones to match with jewels.

terminal

Solution

Solution 1: Hash Table or Array

We can first use a hash table or array $s$ to record all types of jewels. Then traverse all the stones, and if the current stone is a jewel, increment the answer by one.

1

2

3

4

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

Continue Practicing

#770 basic calculator iv #767 reorganize string #763 partition labels