Jewels and Stones

Jewels and Stones

1. What is this problem about?

The Jewels and Stones interview question is a classic string counting problem. You are given two strings: jewels, where each character represents a type of stone that is a jewel, and stones, representing the stones you have. Your goal is to count how many of your stones are also jewels. Note that characters are case-sensitive.

2. Why is this asked in interviews?

This is one of the most common introductory questions at Amazon, Apple, and Google. It tests your knowledge of Hash Table interview patterns and the basic time complexity of different data structures. It evaluations if you know that searching in a Set is $O(1)$, while searching in a string or array is $O(N)$.

3. Algorithmic pattern used

This problem follows the Hash Set for Membership pattern.

1. Set Construction: Convert the jewels string into a Hash Set of characters.
2. Counting Pass: Iterate through the stones string character by character.
3. Membership Check: For each stone, check if it exists in the jewels set.
4. Summation: Increment a counter for every match found.

4. Example explanation

jewels = "aA", stones = "aAAbbbb"

1. jewelSet = {'a', 'A'}.
2. Traverse stones:
   • 'a': in set. Count = 1.
   • 'A': in set. Count = 2.
   • 'A': in set. Count = 3.
   • 'b': not in set. ... Result: 3.

5. Common mistakes candidates make

• $O(N \cdot M)$ Brute Force: Using nested loops to check every stone against every jewel. While it works for tiny strings, it’s not the optimal $O(N+M)$ solution.
• Case Insensitivity: Forgetting that 'a' and 'A' are distinct types of stones.
• Redundant Set Creation: Re-creating the set inside the loop or using a list instead of a set for lookups.

6. Interview preparation tip

Even for "Easy" problems, mention the Time and Space Complexity. Time is $O(N+M)$ where $N$ is number of jewels and $M$ is number of stones. Space is $O(N)$ to store the jewels. This demonstrates a professional approach to even simple tasks.