Jewels and Stones solution and explanation
Google
9 more videos on this problem
Jewels and Stones - Leetcode 771 - Hashmaps & Sets (Python)Greg Hogg · 6:52 · 25K views
Jewels and stones | Leetcode #771Techdose · 4:49 · 11K views
Jewels and Stones (LeetCode 771) | Full solution with examples and visuals | Study AlgorithmsNikhil Lohia · 9:00 · 7K views
Leetcode | 771. Jewels and Stones | Easy | Java SolutionDeveloper Docs · 4:30 · 1K views
Solving LeetCode 771 in JavaScript (Jewels and Stones)KA Education · 4:41 · 1K views
LEETCODE SOLUTION 771 | Jewels and Stones | Leetcode for BEGINNERS | EASY | Javascript |CodingForBeginners · 8:40 · 465 views
Jewels and Stones | LeetCode 771 | CppCodeClips with Abhishek Ranjan · 2:52 · 322 views
771. Jewels and Stones | Leetcode | PythonAbdullah Arshed · 2:39 · 284 views
771 Jewels and Stones LeetCode JavaScript Hash TableSantamaria Code · 4:34 · 250 views
How to Solve 771 Jewels and Stones on LeetCode (Javascript)Becoming A Better Dev (with David) · 5:42 · 161 views
The problem
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 <= 50jewelsandstonesconsist of only English letters.- All the characters of
jewelsare unique.
Approach overview
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 1: Using a Set for Fast Lookup
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.
def numJewelsInStones(jewels, stones):
jewel_set = set(jewels)
return sum(stone in jewel_set for stone in stones)
print(numJewelsInStones('aA', 'aAAbbbb'))import java.util.HashSet;
import java.util.Set;
public class JewelStones {
public int numJewelsInStones(String jewels, String stones) {
Set<Character> jewelSet = new HashSet<>();
for (char jewel : jewels.toCharArray()) {
jewelSet.add(jewel);
}
int count = 0;
for (char stone : stones.toCharArray()) {
if (jewelSet.contains(stone)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
JewelStones solution = new JewelStones();
System.out.println(solution.numJewelsInStones("aA", "aAAbbbb"));
}
}#include <iostream>
#include <unordered_set>
int numJewelsInStones(std::string jewels, std::string stones) {
std::unordered_set<char> jewelSet(jewels.begin(), jewels.end());
int count = 0;
for (char stone : stones) {
if (jewelSet.count(stone)) {
count++;
}
}
return count;
}
int main() {
std::string jewels = "aA";
std::string stones = "aAAbbbb";
std::cout << numJewelsInStones(jewels, stones) << std::endl;
return 0;
}function numJewelsInStones(jewels, stones) {
const jewelSet = new Set(jewels);
let count = 0;
for (const stone of stones) {
if (jewelSet.has(stone)) {
count++;
}
}
return count;
}
console.log(numJewelsInStones('aA', 'aAAbbbb'));#include <stdio.h>
#include <stdbool.h>
bool isJewel(char c, char *jewels) {
for (int i = 0; jewels[i] != '\0'; i++) {
if (c == jewels[i]) {
return true;
}
}
return false;
}
int numJewelsInStones(char *jewels, char *stones) {
int count = 0;
for (int i = 0; stones[i] != '\0'; i++) {
if (isJewel(stones[i], jewels)) {
count++;
}
}
return count;
}
int main() {
char *jewels = "aA";
char *stones = "aAAbbbb";
printf("%d\n", numJewelsInStones(jewels, stones));
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int NumJewelsInStones(string jewels, string stones) {
var jewelSet = new HashSet<char>(jewels);
int count = 0;
foreach (var stone in stones) {
if (jewelSet.Contains(stone)) {
count++;
}
}
return count;
}
static void Main() {
Console.WriteLine(NumJewelsInStones("aA", "aAAbbbb"));
}
}The Python solution utilizes the set data structure, providing efficient O(1) lookups for each stone. The use of a generator expression with sum() simplifies the counting process.
Time Complexity: O(n + m), where n is the number of stones and m is the size of the set represented by the jewels. Space Complexity: O(m), for storing jewels in a set.
Approach 2: Using Array for Character Indexing
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.
def numJewelsInStones(jewels, stones):
jewel_count = [0] * 52
for jewel in jewels:
if 'a' <= jewel <= 'z':
jewel_count[ord(jewel) - ord('a')] = 1
else:
jewel_count[ord(jewel) - ord('A') + 26] = 1
count = 0
for stone in stones:
if 'a' <= stone <= 'z':
count += jewel_count[ord(stone) - ord('a')]
else:
count += jewel_count[ord(stone) - ord('A') + 26]
return count
print(numJewelsInStones('aA', 'aAAbbbb'))public class JewelStones {
public int numJewelsInStones(String jewels, String stones) {
int[] jewelCount = new int[52];
for (char jewel : jewels.toCharArray()) {
if (jewel >= 'a' && jewel <= 'z')
jewelCount[jewel - 'a'] = 1;
else
jewelCount[jewel - 'A' + 26] = 1;
}
int count = 0;
for (char stone : stones.toCharArray()) {
if (stone >= 'a' && stone <= 'z') {
count += jewelCount[stone - 'a'];
} else {
count += jewelCount[stone - 'A' + 26];
}
}
return count;
}
public static void main(String[] args) {
JewelStones solution = new JewelStones();
System.out.println(solution.numJewelsInStones("aA", "aAAbbbb"));
}
}#include <iostream>
#include <vector>
int numJewelsInStones(std::string jewels, std::string stones) {
std::vector<int> jewelCount(52, 0);
int count = 0;
for (char jewel : jewels) {
if (jewel >= 'a' && jewel <= 'z')
jewelCount[jewel - 'a'] = 1;
else
jewelCount[jewel - 'A' + 26] = 1;
}
for (char stone : stones) {
if (stone >= 'a' && stone <= 'z') {
count += jewelCount[stone - 'a'];
} else {
count += jewelCount[stone - 'A' + 26];
}
}
return count;
}
int main() {
std::string jewels = "aA";
std::string stones = "aAAbbbb";
std::cout << numJewelsInStones(jewels, stones) << std::endl;
return 0;
}function numJewelsInStones(jewels, stones) {
const jewelCount = new Array(52).fill(0);
for (const jewel of jewels) {
if (jewel >= 'a' && jewel <= 'z')
jewelCount[jewel.charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
else
jewelCount[jewel.charCodeAt(0) - 'A'.charCodeAt(0) + 26] = 1;
}
let count = 0;
for (const stone of stones) {
if (stone >= 'a' && stone <= 'z') {
count += jewelCount[stone.charCodeAt(0) - 'a'.charCodeAt(0)];
} else {
count += jewelCount[stone.charCodeAt(0) - 'A'.charCodeAt(0) + 26];
}
}
return count;
}
console.log(numJewelsInStones('aA', 'aAAbbbb'));#include <stdio.h>
#include <string.h>
int numJewelsInStones(char *jewels, char *stones) {
int jewelCount[52] = {0};
int count = 0;
for (int i = 0; jewels[i] != '\0'; i++) {
if (jewels[i] >= 'a' && jewels[i] <= 'z')
jewelCount[jewels[i] - 'a'] = 1;
else
jewelCount[jewels[i] - 'A' + 26] = 1;
}
for (int i = 0; stones[i] != '\0'; i++) {
if (stones[i] >= 'a' && stones[i] <= 'z') {
count += jewelCount[stones[i] - 'a'];
} else {
count += jewelCount[stones[i] - 'A' + 26];
}
}
return count;
}
int main() {
char *jewels = "aA";
char *stones = "aAAbbbb";
printf("%d\n", numJewelsInStones(jewels, stones));
return 0;
}using System;
class Program {
public static int NumJewelsInStones(string jewels, string stones) {
int[] jewelCount = new int[52];
foreach (var jewel in jewels) {
if (jewel >= 'a' && jewel <= 'z')
jewelCount[jewel - 'a'] = 1;
else
jewelCount[jewel - 'A' + 26] = 1;
}
int count = 0;
foreach (var stone in stones) {
if (stone >= 'a' && stone <= 'z') {
count += jewelCount[stone - 'a'];
} else {
count += jewelCount[stone - 'A' + 26];
}
}
return count;
}
static void Main() {
Console.WriteLine(NumJewelsInStones("aA", "aAAbbbb"));
}
}The Python solution uses an indexed array for character analysis, distinguishing letters using ASCII values. This indexed approach facilitates concise membership checks.
Time Complexity: O(n + m), where n and m are the lengths of jewels and stones, respectively. Space Complexity: O(1), involving a size-fixed integer array.
Approach 3: 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.
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.
function numJewelsInStones(jewels: string, stones: string): number {
const s = new Set([...jewels]);
let ans = 0;
for (const c of stones) {
s.has(c) && ans++;
}
return ans;
}func numJewelsInStones(jewels string, stones string) (ans int) {
s := [128]int{}
for _, c := range jewels {
s[c] = 1
}
for _, c := range stones {
ans += s[c]
}
return
}use std::collections::HashSet;
impl Solution {
pub fn num_jewels_in_stones(jewels: String, stones: String) -> i32 {
let mut s = jewels.as_bytes().iter().collect::<HashSet<&u8>>();
let mut ans = 0;
for c in stones.as_bytes() {
if s.contains(c) {
ans += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Set for Fast Lookup | Time Complexity: O(n + m), where n is the number of stones and m is the size of the set represented by the jewels. Space Complexity: O(m), for storing jewels in a set. |
| Using Array for Character Indexing | Time Complexity: O(n + m), where n and m are the lengths of jewels and stones, respectively. Space Complexity: O(1), involving a size-fixed integer array. |
| Hash Table or Array | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Jewels and Stones easy or hard?
Jewels and Stones is categorized as an Easy problem. The challenge focuses on recognizing that repeated membership checks should use a hash-based structure instead of nested loops.
How to solve Jewels and Stones in O(n)?
Treat the jewels string as a lookup structure. Store each jewel character in a hash set, then iterate through stones and increment a counter whenever a character exists in the set. Each membership check is O(1) on average, so the total runtime becomes O(n + m).
What is the best approach for Jewels and Stones?
The hash set approach is the most common solution. Insert all characters from the jewels string into a set, then scan the stones string and count characters that appear in the set. This gives O(n + m) time complexity with O(m) extra space and keeps the implementation simple across languages.
What data structure is used in Jewels and Stones?
The most common data structure is a hash set (or hash table) used for constant-time membership checks. Some implementations also use a fixed-size boolean array indexed by character code when the character set is known.
What is the time complexity of Jewels and Stones?
The optimal solution runs in O(n + m) time, where n is the length of the stones string and m is the length of the jewels string. Building the lookup structure takes O(m), and scanning all stones requires O(n).
Is Jewels and Stones asked at Google, Amazon, or Meta?
Jewels and Stones is a common introductory interview problem used by companies such as Amazon and Google to test basic understanding of hash sets and string iteration. It checks whether candidates recognize constant-time lookup patterns.