Jewels and Stones

easy hash map string

Problem

Given a string jewels of distinct jewel types and a string stones, return the number of stones that are jewels.

Inputjewels = "aA", stones = "aAAbbbb"

Output3

Stones 'a', 'A', 'A' are jewels; the four 'b's are not.

jewels

stones

def num_jewels_in_stones(jewels, stones):
    j = set(jewels)
    count = 0
    for c in stones:
        if c in j:
            count += 1
    return count

function numJewelsInStones(jewels, stones) {
  const j = new Set(jewels);
  let count = 0;
  for (const c of stones) {
    if (j.has(c)) count++;
  }
  return count;
}

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> j = new HashSet<>();
        for (char c : jewels.toCharArray()) j.add(c);
        int count = 0;
        for (char c : stones.toCharArray()) {
            if (j.contains(c)) count++;
        }
        return count;
    }
}

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<char> j(jewels.begin(), jewels.end());
        int count = 0;
        for (char c : stones) {
            if (j.count(c)) count++;
        }
        return count;
    }
};

Explanation

We need to count how many characters in stones are jewels. The naive way would re-scan jewels for every stone, but a hash set lets us answer "is this a jewel?" instantly.

So we first drop every jewel character into a set j = set(jewels). Then we make one pass over stones, adding 1 to count whenever the current character is found in the set.

The set membership test c in j is effectively O(1), so the total work is just the size of the two strings.

Example: jewels = "aA" becomes the set {a, A}. Scanning stones = "aAAbbbb": a, A, A are jewels (count reaches 3), while the four b's are not. Answer 3.

Note that case matters here — a and A are different jewels, which the set handles naturally.

Time: O(|J| + |S|) Space: O(|J|)