Jewels and Stones Leetcode Solution

The problem Jewels and Stones Leetcode Solution states that you are given two strings. One of them represents jewels and one of them represents stones. The string that contains jewels represents the characters that are jewels. We need to find the number of characters in the stones string that are jewels. So, let’s take a look at a few examples.

jewels = "aA", stones = "aAAbbbb"

3

Explanation: As we can see from the stones string, there are two instances of ‘A’, and one instance of ‘a’. Thus there are a total of 3 jewels in the stones string. Hence the answer.

jewels = "z", stones = "ZZ"

0

Explanation: Since there is a single lowercase ‘z’ in the jewels string. And there are two uppercase ‘Z’ in the stones string. Since the checking is case sensitive. There are no jewels in the stones string.

Brute Force Approach for Jewels and Stones Leetcode Solution

The problem Jewels and Stones Leetcode Solution asks us to find the number of jewels in the stones string. We can do a linear search to find the number of jewels. We will use two nested for loops that check if the current character of the stones string is a jewel. Then if the current character is found to be a jewel, we increment our answer. But the approach is slow since it uses two nested loops.

Brute Force code for Jewels and Stones Leetcode Solution

C++ code

#include<bits/stdc++.h>
using namespace std;

int numJewelsInStones(string jewels, string stones) {
    int answer = 0;
    for(int i=0; i<stones.length();i++){
        for(int j=0;j<jewels.length();j++){
            if(stones[i] == jewels[j])
                answer++;
        }
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}

3

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        int answer = 0;
        for(int i=0; i<stones.length();i++){
            for(int j=0;j<jewels.length();j++){
                if(stones.charAt(i) == jewels.charAt(j))
                    answer++;
            }
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}

3

Complexity Analysis

Time Complexity

O(N*M), where N is the length of the jewels string and M is the length of the stones string. Thus the time complexity is polynomial.

Space Complexity

O(1), since we do not use any array or vector. We are using only constant space. Thus the brute approach has constant space complexity.

Optimized Approach for Jewels and Stones Leetcode Solution

Since the brute force approach is slow. We try to optimize the above approach using HashSet. We use a HashSet to store the characters from the jewels string. The for loop which we used to check if the current character from the stones string is a jewel, can now be checked in O(1) time. This optimization is because of using the HashSet. Now we can simply check if the current character is present in the HashSet. If it is in the HashSet, we increment our answer.

Code

C++ Code

#include<bits/stdc++.h>
using namespace std;

int numJewelsInStones(string jewels, string stones) {
    unordered_set<char> jewelSet;
    for(int i=0;i<jewels.length();i++)
        jewelSet.insert(jewels[i]);

    int answer = 0;
    for(int i=0;i<stones.length();i++){
        if(jewelSet.count(stones[i]) == true)
            answer++;
    }
    return answer;
}

int main(){
    string jewels = "aA", stones = "aAAbbbb";
    cout<<numJewelsInStones(jewels, stones);
}

3

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> jewelSet = new HashSet<Character>();
        for(int i=0;i<jewels.length();i++)
            jewelSet.add(jewels.charAt(i));
        
        int answer = 0;
        for(int i=0;i<stones.length();i++){
            if(jewelSet.contains(stones.charAt(i)) == true)
                answer++;
        }
        return answer;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String jewels = "aA";
    String stones = "aAAbbbb";
    System.out.println(numJewelsInStones(jewels, stones));
  }
}

3

Complexity Analysis

Time Complexity

O(N+M), where N and M is the size of jewels and stones string. The optimization is achieved because we utilized HashSets. Now, the time complexity has been reduced to linear.

Space Complexity

O(N), since we store the characters from the jewels string. The space complexity is dependent on the jewels string size.