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
jewelsandstonesare limited to English letters (both uppercase and lowercase). - The length of both strings is between 1 and 50.
- All characters in
jewelsare 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
- Initialize a Set: Create a set from the
jewelsstring. This will allow us to quickly check if a stone is a jewel. - Count Jewels in Stones: Iterate through each character in the
stonesstring and use the set to check if it is a jewel. If it is, increment a counter. - 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
stonesstring. 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
jewelsstring. 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
jewelsorstonesis empty, the function will correctly return 0 since there are no jewels to count. - All Characters Unique: Since all characters in
jewelsare 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.