771. Jewels and Stones - Leetcode Solution

Leetcode Problem Link Code Solution Link:

Step-by-Step Thought Process

Brute Force

Understand the Problem:
- The task is to find how many characters from the stones string are also present in the jewels string.
- Each stone is checked individually to see if it exists in the jewels string.
Loop Through the Stones:
- We iterate through each character in the stones string.
Check Each Stone Against Jewels:
- For each stone, we check if it exists in the jewels string.
- This requires scanning the jewels string for each stone, resulting in a linear search for every stone.
Count Matches:
- If a stone is found in the jewels string, we increment the counter.
Return the Result:
- After checking all the stones, return the final count.

Code Solution (Brute Force)

class Solution:
    def numJewelsInStones (self, jewels: str, stones: str) -> int:
        count = 0
        for stone in stones:
            if stone in jewels:
                count += 1
        return count

# Time Complexity: O(n * m)
# Space Complexity: O(1)

#include <string>

class Solution {
public:
    int numJewelsInStones(std::string jewels, std::string stones) {
        int count = 0;
        for (char stone : stones) {
            for (char jewel : jewels) {
                if (stone == jewel) {
                    count++;
                    break;
                }
            }
        }
        return count;
        // Time Complexity: O(n * m), n is length of stones, m is length of jewels
        // Space Complexity: O(1)
    }
};

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        for (char stone : stones.toCharArray()) {
            for (char jewel : jewels.toCharArray()) {
                if (stone == jewel) {
                    count++;
                    break;
                }
            }
        }
        return count;
        // Time Complexity: O(n * m), n is length of stones, m is length of jewels
        // Space Complexity: O(1)
    }
}

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let count = 0;
    for (const stone of stones) {
        for (const jewel of jewels) {
            if (stone === jewel) {
                count++;
                break;
            }
        }
    }
    return count;
    // Time Complexity: O(n * m), n is length of stones, m is length of jewels
    // Space Complexity: O(1)
};

Why the Brute Force Solution is Inefficient

The brute force solution is inefficient because for every stone in the stones string, we are performing a membership check against the jewels string. This results in a time complexity of O(n * m), which can be slow when both strings are long.

💡Fixing the Brute Force Solution

Use a Set for Efficient Lookup: In the optimal solution, the jewels string is converted into a set. Sets provide an average O(1) time complexity for membership checks, which significantly reduces the number of operations compared to the brute force solution.

Code Solution (Optimal)

class Solution:
    def numJewelsInStones (self, jewels: str, stones: str) -> int:
        # O(n + m)
        s = set(jewels)
        count = 0
        for stone in stones:
            if stone in s:
                count += 1
        return count

# Time Complexity: O(n + m)
# Space Complexity: O(n)

#include <unordered_set>
#include <string>

class Solution {
public:
    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.find(stone) != jewelSet.end()) {
                count++;
            }
        }

        return count;
    }
};

import java.util.HashSet;

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> jewelSet = new HashSet<>();
        for (char j : jewels.toCharArray()) {
            jewelSet.add(j);
        }

        int count = 0;
        for (char s : stones.toCharArray()) {
            if (jewelSet.contains(s)) {
                count++;
            }
        }

        return count;
    }
}

var numJewelsInStones = function(jewels, stones) {
    const jewelSet = new Set(jewels);
    let count = 0;

    for (const stone of stones) {
        if (jewelSet.has(stone)) {
            count++;
        }
    }

    return count;
};

Detailed Explanation

Understanding the Problem: Jewels and Stones

The “Jewels and Stones” problem is a classic example of frequency analysis and efficient lookup. You're given two strings:

jewels: A string representing the types of stones that are jewels.
stones: A string representing the stones you have, where each character is a type of stone.

The task is to count how many stones are also jewels. For example, given jewels = "aA" and stones = "aAAbbbb", the output should be 3, because there are two 'A's and one 'a' in stones.

Why This Problem Matters

This problem is an excellent introduction to the importance of choosing the right data structure. It demonstrates how sets can optimize search operations, and it forms a foundation for more advanced tasks involving frequency counting, character analysis, and hash-based membership checking.

Naive Approach: Brute Force

The brute-force method loops through each character in the stones string and, for each one, checks if it exists in the jewels string. Since jewels is treated as a normal string, each check takes O(m) time (where m is the length of the jewels string). If there are n characters in stones, the total time complexity becomes O(n × m).

Optimal Approach: Using a Set for Faster Lookup

To improve performance, we can convert the jewels string into a set. Sets in most programming languages provide average O(1) lookup time. This turns the nested loop into a single pass through the stones string.

Here’s the optimized process:

Convert jewels to a set called jewelSet.
Initialize a counter to 0.
Loop through each character stone in stones.
If stone is in jewelSet, increment the counter.
Return the final count.

Example Walkthrough

Input: jewels = "aA", stones = "aAAbbbb"

Create jewelSet = {'a', 'A'}
Loop through stones: 'a' → ✔️, 'A' → ✔️, 'A' → ✔️, 'b' → ✖️, 'b' → ✖️, 'b' → ✖️, 'b' → ✖️
Total jewels in stones = 3

Time and Space Complexity

Time Complexity: O(n + m), where n is the length of stones and m is the length of jewels. Creating the set takes O(m), and scanning the stones takes O(n).
Space Complexity: O(m) to store the jewelSet.

Edge Cases to Consider

If jewels is empty → result is always 0.
If stones is empty → result is always 0.
If both are empty → result is 0.
Case sensitivity matters: 'a' and 'A' are treated as different characters.

Conclusion

The “Jewels and Stones” problem is a simple but powerful illustration of how using the right data structure can transform a slow brute-force solution into an efficient one. It introduces core concepts like hash set lookup, character iteration, and membership testing—all of which are vital for handling real-world data efficiently.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?