Jewels and Stones
EasyPrompt
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: 3Example 2:
Input: jewels = "z", stones = "ZZ"
Output: 0
Constraints:
1 <= jewels.length, stones.length <= 50jewelsandstonesconsist of only English letters.- All the characters of
jewelsare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach where we compare every stone against every jewel. We iterate through each character in the stones string, and for each stone, we perform another full iteration through the jewels string to check for a match.
Algorithm
- Initialize a counter
jewelCountto 0. - Iterate through each character
stoneCharin thestonesstring. - For each
stoneChar, start a nested loop to iterate through each characterjewelCharin thejewelsstring. - If
stoneCharis equal tojewelChar, incrementjewelCountand break the inner loop. - After iterating through all stones, return
jewelCount.
Walkthrough
In this method, we use two nested loops. The outer loop iterates over each stone you have, and the inner loop iterates over each type of jewel. For each stone, we check if it matches any of the jewel types. If a match is found, we increment a counter. Since the problem states that all jewel types are unique, we can add a small optimization: once a stone is identified as a jewel, we can stop searching for that particular stone and move on to the next one by breaking the inner loop. Despite this optimization, the fundamental approach remains a pairwise comparison of all stones against all jewels.
class Solution { public int numJewelsInStones(String jewels, String stones) { int jewelCount = 0; for (int i = 0; i < stones.length(); i++) { char stoneChar = stones.charAt(i); for (int j = 0; j < jewels.length(); j++) { char jewelChar = jewels.charAt(j); if (stoneChar == jewelChar) { jewelCount++; break; // Jewel types are unique, so we can move to the next stone. } } } return jewelCount; }}Complexity
Time
O(S * J) - Where S is the length of `stones` and J is the length of `jewels`. For each of the S stones, we might have to iterate through all J jewels in the worst case.
Space
O(1) - We only use a few variables to store the count and loop indices, which does not depend on the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space (O(1) space complexity).
Cons
Inefficient for large input strings due to its quadratic time complexity.
Performs many redundant comparisons if the
jewelsstring is long.
A more efficient approach is to use a data structure that provides fast lookups. We can first store all the jewel types in a Hash Set. This allows us to check if a stone is a jewel in constant time on average. We iterate through the jewels once to build the set, and then iterate through the stones once to count the matches.
Algorithm
- Create an empty
HashSet<Character>namedjewelSet. - Iterate through the
jewelsstring and add each character to thejewelSet. - Initialize a counter
jewelCountto 0. - Iterate through the
stonesstring. - For each character
stoneChar, check if it is present in thejewelSetusing thecontains()method. - If it is present, increment
jewelCount. - Return
jewelCount.
Walkthrough
The bottleneck in the brute-force approach is the repeated linear scan of the jewels string. We can eliminate this by pre-processing the jewels. We create a HashSet and populate it with all the characters from the jewels string. Building this set takes time proportional to the number of jewel types. After the set is built, we can iterate through the stones string. For each stone, we perform a lookup in the hash set. The contains() operation in a hash set is very fast, taking O(1) time on average. This reduces the overall time complexity from quadratic to linear.
import java.util.HashSet;import java.util.Set; class Solution { public int numJewelsInStones(String jewels, String stones) { Set<Character> jewelSet = new HashSet<>(); for (char j : jewels.toCharArray()) { jewelSet.add(j); } int jewelCount = 0; for (char s : stones.toCharArray()) { if (jewelSet.contains(s)) { jewelCount++; } } return jewelCount; }}Complexity
Time
O(J + S) - Where J is the length of `jewels` and S is the length of `stones`. It takes O(J) time to build the set and O(S) time to iterate through the stones.
Space
O(J) - Where J is the length of `jewels`. We need to store each unique jewel type in the hash set.
Trade-offs
Pros
Significantly faster than the brute-force approach with linear time complexity.
A general-purpose solution that works well for any character set, not just English letters.
Cons
Uses extra space proportional to the number of jewel types.
Has a slight overhead due to hash computation and potential hash collisions, though minimal in practice.
This is the most optimized approach, building upon the hash set idea. Since the problem specifies that the characters are English letters, we can use a simple boolean array as a direct-access table instead of a hash set. This provides the same O(1) lookup time but with better performance due to no hashing overhead and constant space usage.
Algorithm
- Create a boolean array
isJewelof size 128 (to cover ASCII values of English letters) and initialize all elements tofalse. - Iterate through the
jewelsstring. For each characterj, setisJewel[j] = true. - Initialize a counter
jewelCountto 0. - Iterate through the
stonesstring. - For each character
s, check ifisJewel[s]istrue. - If it is, increment
jewelCount. - Return
jewelCount.
Walkthrough
We can leverage the fact that characters have underlying integer representations (ASCII values). We can create a boolean array, say of size 128, which is large enough to cover all uppercase and lowercase English letters. This array will act as a direct map where the index corresponds to a character's ASCII value. First, we iterate through the jewels string and mark the corresponding indices in our boolean array as true. This populates our 'set' of jewels. Then, we iterate through the stones string. For each stone, we check our boolean array at the index corresponding to the stone's character. If the value is true, we increment our count. This array lookup is an O(1) operation, and since the array size is fixed regardless of input size, the space complexity is constant.
class Solution { public int numJewelsInStones(String jewels, String stones) { // 'z' has ASCII value 122. An array of size 128 is sufficient. boolean[] isJewel = new boolean[128]; for (char j : jewels.toCharArray()) { isJewel[j] = true; } int jewelCount = 0; for (char s : stones.toCharArray()) { if (isJewel[s]) { jewelCount++; } } return jewelCount; }}Complexity
Time
O(J + S) - Where J is the length of `jewels` and S is the length of `stones`. It takes O(J) to populate the array and O(S) to check the stones.
Space
O(1) - The space required for the boolean array is constant (e.g., 128 booleans) and does not scale with the size of the input strings.
Trade-offs
Pros
Extremely efficient with linear time complexity.
Constant space complexity, as the array size does not depend on the input length.
Typically faster in practice than a hash set due to direct memory access without hashing overhead.
Cons
This approach is specialized for a known, small character set (like ASCII). It is less flexible than a hash set if the character set were large or unknown (e.g., full Unicode).
Solutions
Solution
class Solution { public int numJewelsInStones ( String jewels , String stones ) { int [] s = new int [ 128 ]; for ( char c : jewels . toCharArray ()) { s [ c ] = 1 ; } int ans = 0 ; for ( char c : stones . toCharArray ()) { ans += s [ c ]; } return ans ; } }/** * @param {string} jewels * @param {string} stones * @return {number} */ var numJewelsInStones = function (jewels, stones) { const s = new Set(jewels.split("")); return stones.split("").reduce((prev, val) => prev + s.has(val), 0); };class Solution { public: int numJewelsInStones ( string jewels , string stones ) { int s [ 128 ] = { 0 }; for ( char c : jewels ) s [ c ] = 1 ; int ans = 0 ; for ( char c : stones ) ans += s [ c ]; return ans ; } };class Solution : def numJewelsInStones ( self , jewels : str , stones : str ) -> int : s = set ( jewels ) return sum ( c in s for c in stones )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.