Related Tags

beginner
programming
c++
communitycreator

# Jewels 💎 and stones ⛰ in C++

Austin

Here is a rocking problem that shows how to deal with arrays.

You’re given the string J, representing the types of stones that are jewels, and S, representing the stones you have. Each character in S is a type of stone you have. You want to know how many of your stones are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.

## Example 1

Input: J = "aA", S = "aAAbbbb"
Output: 3


## Example 2

Input: J = "z", S = "ZZ"
Output: 0


## Brute force 👊

Looking at a brute force method, I would use a double for loop, which would increase my Big O notation to the length of S multiplied by length J, $O(S * J)$. Here, I would have to iterate through the stones multiple times for each jewel I am referencing.

#include <iostream>
using namespace std;

int numJewelsInStones(string J, string S) {
int count = 0;
for(int jewel = 0; jewel<J.length(); jewel++){
for(int stone = 0; stone < S.length(); stone++){
if(J[jewel] == S[stone]){
count++;
}
}
}
return count;
}

int main(){
string J = "aA";
string S = "aAAbbbb";
int count = numJewelsInStones(J, S);
cout << count << endl;
}

## An optimal solution

Looking at this problem, what comes to mind is using some sort of hashmap or set. Today, I’m going to be switching it up and using C++. In C++, there is a structure you can take advantage of known as an unordered_set. This will let us store unique values in a container based on a key 🔑. Looking at this problem, I can make the jewels my unordered set and search them quickly. This will also allow me to decrease my time complexity to the length of S plus length J, $O(S + J)$.

#include <iostream>
#include <unordered_set>
using namespace std;

int numJewelsInStones(string J, string S) {
unordered_set<char> jewels;
int total = 0;
for(int index = 0; index < J.size(); index++){
if(jewels.find(J[index]) == jewels.end()){
jewels.insert(J[index]);
}
}
for(int index = 0; index < S.size(); index++){
if(jewels.find(S[index]) != jewels.end()){
total++;
}
}
}

int main(){
string J = "aA";
string S = "aAAbbbb";
int count = numJewelsInStones(J, S);
cout << count << endl;
}

Follow me on GitHub to see what I am working on. Thanks for reading and follow me here for more articles! 🙃

RELATED TAGS

beginner
programming
c++
communitycreator

CONTRIBUTOR

Austin
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time