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.
This approach leverages a Set (or a HashSet in some languages) for quickly determining if a stone is a jewel. The idea is to store all the jewel types in a set, then iterate through each stone, checking if the stone is in the set. If it is, we increment our count of jewels found.
In the C implementation, we define a helper function isJewel that checks if a character is a jewel by iterating through the jewel string. For each stone, we call this function and increment our count accordingly. This is not the most optimized as it involves iterating through the jewels for each stone.
Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings.
This approach uses an array to quickly map each character to an index, allowing us to count frequencies of jewels in the stones. Since the input is restricted to English letters, a fixed-size array of 52 (for each upper and lower case letter) is adequate.
This C solution uses an array of size 52 to represent each letter as a potential jewel. This approach handles both uppercase and lowercase characters distinctly, using ASCII arithmetic to map letters to indices.
Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping.
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.
Time complexity is O(m+n), and space complexity is O(|\Sigma|), where m and n are the lengths of the strings jewels and stones respectively, and \Sigma is the character set, which in this problem is the set of all uppercase and lowercase English letters.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
| Approach | Complexity |
|---|---|
| Using a Set for Fast Lookup | Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings. |
| Using Array for Character Indexing | Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping. |
| Hash Table or Array | — |
| 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. |
ROOKIE DEVELOPER vs Quirky Senior Engineer on Jewels and Stones, Leetcode 771 • Greg Hogg • 607,759 views views
Watch 9 more video solutions →Practice Jewels and Stones with our built-in code editor and test cases.
Practice on FleetCode