Jewels and Stones - LeetCode 771 Solution

Problem Overview

#

The Jewels and Stones problem from LeetCode asks you to count how many stones are jewels.

Problem Statement: You’re given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a stone you have. You want to know how many of the stones you have are also jewels. The jewels are case-sensitive, so the same letter as different cases is considered different types.

Example:

• Input: jewels = "aB", stones = "aAbBcCcD"

• Output: 3 (stones ‘a’, ‘A’, and ‘b’ are jewels)

• Input: jewels = "z", stones = "ZZ"

• Output: 0

Solution Approach

#

C# Solution - Using HashSet

#

Create a HashSet from the jewels string for O(1) lookup performance. Before processing, validate that both inputs are not null or empty. Then iterate through each stone and check if it exists in the jewel set. Count each stone that matches a jewel type and return the total count.

public class Solution {
    public int NumJewelsInStones(string jewels, string stones) {
        if(string.IsNullOrEmpty(jewels) || string.IsNullOrEmpty(stones))
            return 0;

        var count = 0;
        var jSet = new HashSet<char>(jewels);

        foreach(var c in stones) {
            // perform search
            if(jSet.Contains(c))
                count++;
        }

        return count;
    }
}

Time Complexity: O(m + n) - where m is jewels length, n is stones length (create set O(m), iterate stones O(n)) Space Complexity: O(1) - at most 52 characters (26 lowercase + 26 uppercase) in the HashSet

Key Insights

#

1. Case Sensitive: ‘a’ and ‘A’ are different jewel types - the comparison is case-sensitive
2. HashSet Creation: Convert jewels string to a HashSet for O(1) average lookup time
3. Input Validation: Check for null or empty strings to handle edge cases before processing
4. Efficient Counting: Iterate through stones once and check each character against the jewel set
5. Fixed Alphabet: Limited to alphabetic characters (at most 52 types), making space complexity constant
6. Early Exit: No need to process further if jewels or stones are empty

Related Problems

#

• Contains Duplicate
• Valid Anagram
• Majority Element

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.