algoadvance

Leetcode 771. Jewels and Stones

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 type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so “a” is considered a different type of stone from “A”.

Clarifying Questions

  1. Can the jewels and stones strings be empty?
    • Yes, they can be empty. In that case, the result would be 0.
  2. Can there be duplicate characters in the jewels string?
    • No, each character in jewels is unique.
  3. Are there any constraints on the length of jewels and stones?
    • Yes, the problem states that both strings will consist of only upper and lower case English letters and their lengths will be at most 50.

Strategy

  1. Use a Hash Set for Jewels:
    • Convert the jewels string into a HashSet for O(1) average-time complexity lookups.
  2. Iterate through Stones:
    • For each character in the stones string, check if it exists in the HashSet of jewels.
    • Count how many times this check is true.
  3. Return the count:
    • This count will represent the number of jewels present in the stones string.

Code

import java.util.HashSet;

public class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        // Create a HashSet from jewels characters
        HashSet<Character> jewelSet = new HashSet<>();
        for (char jewel : jewels.toCharArray()) {
            jewelSet.add(jewel);
        }
        
        // Count jewels in stones
        int count = 0;
        for (char stone : stones.toCharArray()) {
            if (jewelSet.contains(stone)) {
                count++;
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Test cases
        System.out.println(solution.numJewelsInStones("aA", "aAAbbbb")); // Output: 3
        System.out.println(solution.numJewelsInStones("z", "ZZ"));        // Output: 0
        System.out.println(solution.numJewelsInStones("", "ZZ"));         // Output: 0
        System.out.println(solution.numJewelsInStones("z", ""));          // Output: 0
    }
}

Time Complexity

Space Complexity

This solution efficiently calculates the number of jewels in the stones string using a HashSet for optimization.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI