Watch 10 video solutions for Jewels and Stones, a easy level problem involving Hash Table, String. This walkthrough by Greg Hogg has 607,759 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 the stones you have are also jewels.
Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: jewels = "aA", stones = "aAAbbbb" Output: 3
Example 2:
Input: jewels = "z", stones = "ZZ" Output: 0
Constraints:
1 <= jewels.length, stones.length <= 50jewels and stones consist of only English letters.jewels are unique.Problem Overview: You receive two strings: jewels and stones. Each character represents a type of stone. Characters in jewels are the types considered valuable. The task is to count how many characters in stones also appear in jewels. Matching is case-sensitive, so 'a' and 'A' represent different types.
Approach 1: Using a Set for Fast Lookup (O(n + m) time, O(m) space)
The cleanest solution uses a hash set. First insert every character from jewels into a set. This preprocessing step takes O(m) time where m is the length of the jewels string. Then iterate through the stones string and check if each character exists in the set. Hash set membership checks run in O(1) average time, so scanning n stones gives a total time complexity of O(n + m). The extra memory used by the set is O(m). This approach works well because it converts repeated string comparisons into constant-time lookups using a hash table. For most interview settings, this is the expected solution since it is both simple and optimal.
Approach 2: Using Array for Character Indexing (O(n + m) time, O(1) space)
If the character set is limited (for example ASCII letters), an indexed array can replace the hash set. Create a boolean array where each index corresponds to a character code. Iterate through jewels and mark the corresponding indices as true. Next, iterate through stones; for each character, compute its index and check whether it was marked. Increment the count whenever a marked index is found. This approach still runs in O(n + m) time but uses constant space O(1) because the array size is fixed. It avoids hashing overhead and can be slightly faster in lower-level languages like C or C++. The logic relies on direct character indexing within a string.
Recommended for interviews: The hash set solution is the one interviewers usually expect. It demonstrates that you recognize the pattern of converting repeated membership checks into constant-time lookups using a hash table. Mentioning the array-index optimization shows deeper awareness of character constraints and memory tradeoffs, but the set-based approach is typically the clearest and most portable across languages.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set for Fast Lookup | O(n + m) | O(m) | General case. Clean and language-agnostic solution using hash set membership checks. |
| Array Character Indexing | O(n + m) | O(1) | When the character set is fixed (ASCII/letters). Slightly faster and memory-predictable. |