Jewels And Stones In C++

The Gems and Rocks challenge is a popular coding scenario often encountered during interviews. It requires determining the ratio of gems present in the rocks. The goal is to identify the characters in string S that match those in string J. By utilizing an unordered_set to store gem varieties, quick searches can be facilitated, making it feasible to tackle this problem effectively using C++. This strategy involves iterating through J once to populate the set and traversing S once to calculate the number of jewels, ensuring optimal time complexity.

Now, the problem statement is:

We are given two strings:

• ✅ The letter J represents the kind of stones that are regarded as jewels.
• ✅ The stones are represented by the letter S.
• ✅ Each letter in J represents a distinct type of diamond. Each letter in S represents a stone we own. The issue is figuring out how many of the stones in S are also jewels.

Example:

J = "aA", S = "aAAbbbb"

The stones consist of AAbbbb, whereas the diamonds are a and A. Within the set S, there are three jewels: two AA and one a.

Solution for above code using C++ :

Iterating over the stones and maintaining a hash set to store unique jewel types is a practical approach for determining the total count of gems.

Key Steps:

• ✅ Add all of the J (jewels) characters to an unordered batch.
• ✅ Iterate through S (stones) to see if each character appears in the gem collection.
• ✅ If there is a counter, raise it for the gems found.

Time Complexity:

With m representing the size of J and n denoting the size of S, this method operates with a time complexity of O(m + n) as the search and addition to a hash set typically have a complexity of O(1) each.

Example 1:

Let's consider a scenario to demonstrate the concept of Jewels and Stones in the C++ programming language.

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

int numJewelsInStones(std::string J, std::string S) {
    std::unordered_set<char> jewels(J.begin(), J.end());
    int count = 0;

    for (char stone : S) {
        if (jewels.count(stone)) {
            count++;
        }
    }

    return count;
}

int main() {
    std::string J = "aA";
    std::string S = "aAAbbbb";
    std::cout << "Number of jewels in stones: " << numJewelsInStones(J, S) << std::endl;
    return 0;
}

Output:

Number of jewels in stones: 3

Explanation:

• ✅ std::unordered_set jewels(J.begin, J.end);: It uses the characters from J to initialize a collection of gems.
• ✅ Each stone in S is iterated over by the for loop , and if (jewels.count(stone)) determines whether the stone is a jewel.
• ✅ Count++ increases the counter if the condition is true.

Example 2:

Let's explore another example to demonstrate the concept of Jewels and Stones in C++ by utilizing the same string.

#include <iostream>
#include <map>
#include <string>

int numJewelsInStones(std::string J, std::string S) {
    std::map<char, int> jewelMap;
    int count = 0;

    // Mark each character in J as a jewel in the map
    for (char jewel : J) {
        jewelMap[jewel] = 1;
    }

    // Count jewels in S
    for (char stone : S) {
        if (jewelMap[stone] > 0) {
            count++;
        }
    }

    return count;
}

int main() {
    std::string J = "aA";
    std::string S = "aAAbbbb";
    std::cout << "Number of jewels in stones: " << numJewelsInStones(J, S) << std::endl;
    return 0;
}

Output:

Number of jewels in stones: 3

Explanation:

• ✅ Mapping Jewels: The jewelMap uses a value of 1 to mark a character in J as a jewel.
• ✅ Couting jewels in stones: The number of jewels in stones is enhanced if a character in S appears in jewelMap.
• ✅ Output: The total number of diamonds in S is stored in the count variable at the conclusion of the loop.

The time efficiency of this method is O(m + n), with n representing the size of S and m representing the size of J.

Conclusion:

In summary, the Gems and Rocks task serves as a concrete illustration of utilizing hash-based data structures such as unordered_set and map to address search and tallying challenges. By treating gems as distinct characters and leveraging a mechanism for quick searches, the time complexity can be minimized to O(m + n), where m and n represent the lengths of the rock and gem sequences. This strategy underscores the importance of selecting appropriate data structures for specific objectives and establishes a robust groundwork for proficiently handling search tasks, thus serving as a valuable exercise for enhancing debugging and C++ programming effectiveness.