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”.

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Clarifying Questions

  1. Can jewels or stones be empty?
    • Yes, it is possible for either string to be empty. In such cases, the result should be zero.
  2. Can jewels or stones contain characters other than letters?
    • For the purpose of the problem as described, jewels and stones will only contain alphabetic characters (case-sensitive).
  3. What is the maximum length of jewels and stones?
    • Typically, LeetCode problems handle strings up to length of 50 or as specified, but we will assume lengths up to 50 characters unless otherwise constrained.

Strategy

  1. Use a hash set to store all the characters found in jewels for constant time lookup.
  2. Iterate through the stones string and count how many characters are found in the hash set.

Time Complexity

Code

#include <iostream>
#include <unordered_set>
#include <string>

int numJewelsInStones(std::string jewels, std::string stones) {
    std::unordered_set<char> jewelSet(jewels.begin(), jewels.end());
    int count = 0;
    
    for (char stone : stones) {
        if (jewelSet.find(stone) != jewelSet.end()) {
            count++;
        }
    }
    
    return count;
}

int main() {
    std::string jewels = "aA";
    std::string stones = "aAAbbbb";
    std::cout << "Number of jewels in stones: " << numJewelsInStones(jewels, stones) << std::endl;  // Output: 3

    std::string jewels2 = "z";
    std::string stones2 = "ZZ";
    std::cout << "Number of jewels in stones: " << numJewelsInStones(jewels2, stones2) << std::endl;  // Output: 0

    return 0;
}

This code defines a function numJewelsInStones which takes two strings jewels and stones, and returns the number of stones that are also jewels. It leverages an unordered set for efficient look-up of jewel characters and iterates through each stone to check for membership in the jewel set, maintaining an overall O(m + n) time complexity.

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