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