Problem Statement

Given two strings. The first string represents types of jewels, where each character is a unique type of jewel. The second string represents stones you have, where each character represents a type of stone. Determine how many of the stones you have are also jewels.

Examples:

1. Example 1:

   • Input: Jewels = "abc", Stones = "aabbcc"
   • Expected Output: 6
   • Justification: All the stones are jewels.

2. Example 2:

   • Input: Jewels = "aA", Stones = "aAaZz"
   • Expected Output: 3
   • Justification: There are 2 'a' and 1 'A' stones that are jewels.

3. Example 3:

   • Input: Jewels = "zZ", Stones = "zZzZzZ"
   • Expected Output: 6
   • Justification: All the stones are jewels.

Constraints:

• 1 <= jewels.length, stones.length <= 50
• jewels and stones consist of only English letters.
• All the characters of jewels are unique.

Solution

To solve this problem, we can use a HashSet for its property of constant-time lookups. First, we add each character (jewel) from the first string to a HashSet. This set now represents all unique jewels. Next, we iterate through each character (stone) in the second string and check if it is present in the HashSet. If it is, it means this stone is also a jewel. We keep a count of such stones. The final count gives us the total number of stones that are also jewels. The efficiency of this solution lies in the HashSet's ability to quickly check for the presence of a jewel, making the overall process highly efficient for large strings.

1. Populate Jewel Set: Traverse the jewels string and populate a hashset with each character.

2. Count Jewels: Traverse the stones string. For each character, check if it exists in the hashset. If it does, increment a counter.

3. Return Result: After traversing the entire stones string, return the counter.

Using a hashset allows for efficient storage and retrieval of jewel types, ensuring that we can determine the number of jewels in linear time.

Algorithm Walkthrough:

Given the jewels "aA" and the stones "aAaZz":

• Initialize an empty hashset and a counter set to 0.
• Traverse the jewels "aA" and populate the hashset: {'a', 'A'}.
• Traverse the stones "aAaZz". For each character:
  • Check if it exists in the hashset.
  • If it does, increment the counter.
• After traversing all the stones, the counter will be 3, which is the result.

For the third example, with jewels "zZ" and stones "zZzZzZ":

• Initialize an empty hashset and a counter set to 0.
• Traverse the jewels "zZ" and populate the hashset: {'z', 'Z'}.
• Traverse the stones "zZzZzZ". For each character:
  • Check if it exists in the hashset.
  • Since all the stones are jewels in this case, the counter will increment for each stone.
• After traversing all the stones, the counter will be 6, which is the result.

Here is the visual representation of the algorithm: