771. Jewels and Stones

EasyHash TableString
Leetcode Link

Problem Description

In this problem, we are given two strings, jewels and stones. The jewels string represents the types of stones that are considered to be jewels. Each character in the jewels string is a unique jewel type. The stones string contains the stones that we have, and each character represents a type of stone. Our task is to count how many stones we have that are also jewels. It is important to note that the identification of jewels is case sensitive, meaning a and A would be treated as different types of stones.

Intuition

The solution approach involves using a set data structure in Python, which contains only unique items and allows for fast membership testing. By converting the jewels string into a set, we can quickly check if a stone (character in stones string) is a jewel by seeing if it exists in the set.

Here is the intuition behind the steps:

  1. Convert the jewels string into a set. This is important to remove any duplicate characters, which can occur in the input, and to allow for O(1) (constant time) look-ups.
  2. Iterate through each character in the stones string. For every stone, we will check if it's also a jewel.
  3. We check if a stone is a jewel by determining if that stone (character) is present in the jewels set.
  4. Count the number of stones that are jewels. This is done by summing the number of True values yielded by the expression c in s for each stone c in the stones string, where s is the set of jewels.
  5. Return the count as the final answer.

The reasoning behind this approach is centered on set theoryā€”by comparing elements of one set (our stones) to another (our jewels), we're looking for the intersectionā€”the items that are common to both. The use of a set data structure simplifies this search, making the algorithm efficient and concise.

Solution Approach

The implementation of the solution relies on several concepts and data structures, which optimize the process of identifying jewels within the stones. Let's dive into the approach based on the reference solution:

  1. Set Data Structure: The solution begins with creating a set s from the jewels string. Sets are an appropriate choice for two main reasons: they inherently prevent duplicate elements and provide constant time complexity (O(1)) for membership checking. This is crucial because it prevents the algorithm's performance from degrading, even with a large number of jewel types.

    s = set(jewels)
  2. For Loop and Membership Testing: We iterate through each character c in the string stones, which allows us to examine each stone we possess.

    for c in stones:
  3. Boolean Expression in Sum: For every stone represented by character c, we test if it is in the set s (the jewels). The expression c in s evaluates to a boolean (True if c is a jewel, False if not).

    c in s
  4. Sum to Count Trues: The sum function in Python conveniently treats True as 1 and False as 0. Thus, when we sum up the boolean expression results, we effectively count how many times c in s evaluates to True, which corresponds to the number of stones that are jewels.

    sum(c in s for c in stones)
  5. Return the Result: The result of the sum operation is the final answer, which is the number of stones that are also jewels.

Combining these steps in a single expression leads to a compact and efficient solution. The solution's elegance lies in its use of Python's set and iteration mechanisms to directly tie together the question (is this a jewel?) with the answer (how many jewels?).

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        s = set(jewels)
        return sum(c in s for c in stones)

This Python code snippet achieves our goal using advanced concepts in an easy-to-understand and concise way.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simple example to illustrate the solution approach. Suppose we have the following inputs:

  • jewels: "aA"
  • stones: "aAAbbbb"

As per the problem statement, each character in the jewels string is a unique jewel type, and they are case-sensitive. So in this case, we have two types of jewels: 'a' and 'A'. We have to find out how many of the stones are actual jewels.

Following the steps from the solution approach:

  1. Convert the jewels string into a set. Thus, we create a set of jewels s:

    s = set('aA')  # The set will contain {'a', 'A'}
  2. Iterate through each character in the stones string using a for loop:

    for c in "aAAbbbb":
  3. For each character c in stones, check if it is present in the set of jewels s. We'll do this using the expression c in s, which returns True if c is a jewel, otherwise False:

    'a' in s  # True
    'A' in s  # True
    'A' in s  # True
    'b' in s  # False
    'b' in s  # False
    'b' in s  # False
    'b' in s  # False
  4. We evaluate the expression c in s inside a sum() function to add up the True values (which are counted as 1):

    sum(c in s for c in "aAAbbbb")  # This will equal 3
  5. The result of the sum expression (3 in this case) is the number of stones that are also jewels, which is what we return as the answer.

Following this process, we were able to determine that out of the stones we possess ("aAAbbbb"), three of them are jewels ("aAA").

Solution Implementation

1class Solution:
2    def numJewelsInStones(self, jewels: str, stones: str) -> int:
3        # Convert the string jewels into a set for faster lookup
4        jewel_set = set(jewels)
5
6        # Count how many characters in stones are also in jewel_set
7        # The expression (char in jewel_set) returns True if the char is a jewel,
8        # and False otherwise. sum() treats True as 1 and False as 0.
9        jewel_count = sum(char in jewel_set for char in stones)
10
11        # Return the total count of jewels in the stones
12        return jewel_count
13
1class Solution {
2    public int numJewelsInStones(String jewels, String stones) {
3        // An array to keep track of all the ASCII characters. 
4        // The size is 128 as there are 128 ASCII characters.
5        int[] asciiMap = new int[128];
6      
7        // Iterate over the characters in 'jewels' and mark them in the asciiMap.
8        for (char jewel : jewels.toCharArray()) {
9            asciiMap[jewel] = 1;
10        }
11      
12        // 'totalJewels' holds the count of jewels found in 'stones'.
13        int totalJewels = 0;
14      
15        // Iterate over the characters in 'stones'.
16        for (char stone : stones.toCharArray()) {
17            // If a character in 'stones' is marked as 1 in asciiMap, 
18            // it is a jewel, so we increment the totalJewels count.
19            totalJewels += asciiMap[stone];
20        }
21      
22        // Return the total count of jewels found in 'stones'.
23        return totalJewels;
24    }
25}
26
1class Solution {
2public:
3    int numJewelsInStones(string jewels, string stones) {
4        // Array to store whether a character is considered a jewel.
5        // The ASCII value of the character will serve as the index.
6        int jewelFlags[128] = {0}; 
7
8        // Mark the jewels in the 'jewelFlags' array.
9        for (char jewelChar : jewels) {
10            jewelFlags[jewelChar] = 1;
11        }
12
13        // Count variable to keep track of the number of jewels found in 'stones'.
14        int jewelCount = 0;
15
16        // Iterate through each character in 'stones' to see if it's marked as a jewel.
17        for (char stoneChar : stones) {
18            // Increase count if current character is marked as a jewel.
19            jewelCount += jewelFlags[stoneChar];
20        }
21
22        // Return the total count of jewels present in 'stones'.
23        return jewelCount;
24    }
25};
26
1/**
2 * Counts how many stones you have that are also jewels.
3 * @param {string} jewels - The string representing the types of jewels.
4 * @param {string} stones - The string representing the stones you have.
5 * @returns {number} The number of stones that are also jewels.
6 */
7function numJewelsInStones(jewels: string, stones: string): number {
8    // Create a Set to store unique jewel characters for quick lookup
9    const jewelSet = new Set<string>([...jewels]);
10  
11    // Initialize a count variable to keep track of jewels found in stones
12    let count = 0;
13  
14    // Iterate over the stones string to check if a stone is also a jewel
15    for (const stone of stones) {
16        // If the current stone is in the jewel set, increment the count
17        if (jewelSet.has(stone)) {
18            count++;
19        }
20    }
21  
22    // Return the total count of jewels found in stones
23    return count;
24}
25

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n + m) where n is the length of the jewels string and m is the length of the stones string. The creation of the set s from the jewels string takes O(n) time. Then, we iterate over each character c in stones, which takes O(m) time, to check whether it is in the set s. Since set lookup is O(1) on average, the time for the sum operation is also O(m).

Space Complexity

The space complexity is O(n), where n is the length of the jewels string. This is because we create a set s to store the distinct characters in jewels. There is no additional significant space used as we only store a single set.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More