Jewels and Stones

The problem requires us to find out how many stones are also jewels. We’re given a string jewels representing the types of stones that are jewels, and another string stones representing the stones we have.

We can follow these simple steps to solve this problem:

  1. Create a Set of Jewels: Convert the jewels string into a set, allowing us to check if a stone is a jewel in constant time.

  2. Count Jewels in Stones: Iterate through the stones string, and for each stone, check if it is in the set of jewels. Increment a counter for each match.

Code:

1
2
3
4
5
6
7
8

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

Example:

  • jewels = "aA"
  • stones = "aAAbbbb"
  • jewels_set = {"a", "A"}
  • count = 3
  • output = 3

Insights:

  • Efficiency: The time complexity of the algorithm is (O(n)), where (n) is the length of the stones string. Since we have converted the jewels string into a set, the lookup time is constant for each stone.
  • Simplicity: The solution is quite straightforward, using basic string iteration and set membership checking.
  • Case Sensitivity: The problem states that letters are case sensitive, so ‘a’ and ‘A’ are treated as different types of stones. By using a set and directly iterating through the stones, we naturally handle this requirement.

Identifying Problem Isomorphism

“Ransom Note” is a more complex form of “Jewels and Stones”.

In “Jewels and Stones”, you are given strings J representing the types of stones that are jewels, and S representing the stones you have. You need to return the number of stones that you have that are also jewels.

In “Ransom Note”, you are given an arbitrary ransom note string and another string containing letters from all the magazines. You need to decide if the ransom note can be constructed from the magazines. In essence, this problem is asking if all the characters in the first string (ransom note) exist in the second string (magazine).

Both problems involve counting the occurrence of characters from one string in another. However, “Ransom Note” is more complex as it not only requires checking the existence of characters but also ensuring that the count of each character in the ransom note does not exceed the count in the magazine. On the other hand, “Jewels and Stones” only counts the occurrence of characters, which makes it a simpler problem.

“Jewels and Stones” (LeetCode 771) is a simple problem. The problem involves counting the occurrences of characters from one string (jewels) in another string (stones). It’s an excellent problem for learning how to use a HashSet or a similar data structure.

10 Prerequisite LeetCode Problems

If you’re looking for even simpler problems to solve first, consider ones involving basic string manipulation and elementary use of data structures. Here are a few problems that could be a good starting point:

  1. “344. Reverse String”: This problem involves reversing a string, which can be done with a straightforward loop and no additional data structures.
  2. “709. To Lower Case”: This problem requires changing all characters in a string to lowercase.
  3. “804. Unique Morse Code Words”: This problem involves converting strings to Morse code and counting unique results.
  4. “938. Range Sum of BST”: This problem requires a simple traversal of a binary search tree (BST) and summing the nodes that fall within a certain range.
  5. “965. Univalued Binary Tree”: This problem involves checking whether all nodes in a binary tree have the same value.

These problems should provide a basic foundation in string manipulation and elementary use of data structures like HashSets and Trees, which would be beneficial in solving “Jewels and Stones”.

1
2
3
4
5

def numJewelsInStones(jewels: str, stones: str) -> int:
    num = 0
    for i in range(len(jewels)):
        num += stones.count(jewels[i])
    return num

Problem Classification

This problem can be classified within the string and character manipulation in programming. It relates to data structure (strings and characters), algorithms (comparisons and counting), and programming logic.

The ‘What’ components of this problem are:

  1. Two strings - jewels and stones, where each character represents a type of stone.
  2. The task is to count how many of the characters in the stones string are also present in the jewels string.
  3. The problem makes a specific note that letters are case sensitive, i.e., ‘a’ and ‘A’ are considered different types of stones.

The problem can be classified as a ‘count and comparison’ problem within the field of string manipulation. Here, the goal is to compare characters from one string with those in another and keep a count of matching instances. This involves concepts of string handling, character comparison, and counter increment in programming.

The challenge is in implementing an efficient comparison strategy, considering that characters are case sensitive, and creating a counter to keep track of the count of jewels within the stones. This problem also involves understanding and manipulation of basic data structures (strings) and control flow (loops for iteration and conditions for comparison).

Language Agnostic Coding Drills

  1. Dissect the code and identify each distinct concept:

    a) Function Definition: The function numJewelsInStones(jewels: str, stones: str) -> int: encapsulates the code. This introduces the concept of defining a function, setting up parameters, and setting a return type.

    b) Variable Initialization: num = 0 This initializes a counter variable.

    c) Looping: The line for i in range(len(jewels)): introduces the concept of loops and iterating over the length of a string.

    d) String methods: stones.count(jewels[i]) Here, the count() method of string objects is being used. This method returns the number of occurrences of a substring in the given string.

    e) Counters: num += stones.count(jewels[i]) Here, the counter num is being incremented by the count of jewels in stones.

    f) Return statement: return num Here, the function is ending and providing a result.

  2. List of coding concepts or drills in order of increasing difficulty:

    a) Variable Initialization (Easy): It’s one of the first concepts taught in programming.

    b) Function Definition (Easy): Another basic programming concept, though slightly more complex than variable initialization because it involves input parameters and return statements.

    c) Looping (Medium): Looping over a string or array is a core concept in programming. It’s used almost everywhere.

    d) String methods (Medium): Understanding built-in methods like count() requires some familiarity with Python’s String class.

    e) Counters (Medium): Counters are used widely in problems involving collections.

  3. Problem-solving approach that would lead from the problem statement to the final solution:

    a) We start by defining a function that takes two strings as parameters.

    b) Then, we initialize a variable num to 0 which will be used to keep track of the number of jewels in stones.

    c) Using a for loop, we iterate over each character in the string jewels.

    d) Within the loop, we use the string’s count() method to count the occurrences of each jewel in stones, incrementing the counter num by this value each time.

    e) Finally, we return the total count of jewels in stones.

Targeted Drills in Python

  1. Individual Python code that encapsulates each identified concept:

    a) Variable Initialization:

    1
2

    num = 0
print(num)

    b) Function Definition:

    1
2
3
4

    def say_hello(name: str) -> None:
    print(f"Hello, {name}!")

say_hello("Alice")

    c) Looping:

    1
2

    for i in range(5):
    print(i)

    d) String methods:

    1
2
3

    text = "Hello, world!"
count = text.count('o')
print(count)

    e) Counters:

    1
2
3
4
5

    count = 0
for i in range(10):
    if i % 2 == 0:  # If 'i' is even
        count += 1
print(count)

  2. The problem-specific concept for this problem is the use of the string count() method to count the number of occurrences of a specific character in a string. This drill is essential for our problem because we need to count the number of occurrences of each jewel in the stones string.

    Here’s a coding drill for this concept:

    1
2
3
4

    jewels = 'aA'
stones = 'aAAbbbb'
for jewel in jewels:
    print(f"{jewel}: {stones.count(jewel)}")

  3. Now, let’s see how these drills can be integrated together to solve the problem.

    a) Begin by defining a function numJewelsInStones that takes in two parameters - jewels and stones. These represent the types of stones that are jewels and the stones you have, respectively.

    b) Inside this function, initialize a counter variable num to 0. This will keep track of the total number of jewels in the stones.

    c) Set up a for loop to iterate over each character (i.e., each jewel type) in the jewels string.

    d) Inside the loop, use the string count() method to count the number of occurrences of the current jewel type in the stones string. Increment the counter num by this value.

    e) After the loop has finished executing, the function should return the counter num, which represents the total number of jewels in the stones.

This way, we start with basic concepts like variable initialization and function definition, move to core programming concepts like loops and counters, and finally integrate a problem-specific concept to solve the given problem.