Jewels and Stones

Problem Statement

In this problem, you are provided with two strings: jewels and stones. The jewels string represents the types of stones that are considered jewels. Each character in the string stones represents a type of stone that you possess. The task is to count how many of the stones you own are also jewels.

The distinction between jewel types is case-sensitive, meaning that 'a' and 'A' are treated as different types of jewels or stones.

Examples

Example 1

Input:

jewels = "aA", stones = "aAAbbbb"

Output:

3

Example 2

Input:

jewels = "z", stones = "ZZ"

Output:

0

Constraints

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

Approach and Intuition

To solve this problem, the primary task is to identify the characters in the stones string that also appear in the jewels string and count these occurrences.

• Step 1:

  • Convert the string jewels into a set data structure. This transformation is beneficial because set lookup operations (to check if an item exists) are on average more efficient than list lookup operations, specifically O(1) on average for sets compared to O(n) for lists.

• Step 2:

  • Iterate over each character in the string stones. For each of these characters, check if it exists in the "jewels" set created from the first step.

• Step 3:

  • Maintain a count for every character in stones that matches a character in the jewels set.

Expected Performance:

• The time complexity is O(N) where N is the length of the stones string, given that each set operation/check is O(1) on average. This makes the approach efficient even for the upper limit of inputs according to provided constraints.

Handling Case Sensitivity:

• Since the problem specifies that letters are case-sensitive, our method inherently adheres to this as both 'a' and 'A' would be treated as distinct characters in the sets and during comparisons.

Using the above approach, let's analyze the given examples:

• For Example 1:

  • Here, jewels = "aA" and stones = "aAAbbbb". The setup prompts us to count all occurrences of 'a' and 'A' in the stones string: four 'b's are ignored, two 'A's and one 'a' are counted, making a total of 3.

• For Example 2:

  • In this scenario, jewels = "z" but the stones = "ZZ" contains no 'z'. Hence the output is 0 because none of the stone characters match any jewel type from jewels.

With this approach, you can efficiently determine how many stones in your possession are also considered jewels based on the criteria provided.

Solutions

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

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