Scale Engineer

Jewels and Stones

Easy
#0725Time: O(S * J) - Where S is the length of `stones` and J is the length of `jewels`. For each of the S stones, we might have to iterate through all J jewels in the worst case.Space: O(1) - We only use a few variables to store the count and loop indices, which does not depend on the input size.
Data structures
Hash TableString

Prompt

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

 

Constraints:

  • 1 <= jewels.length, stones.length <= 50
  • jewels and stones consist of only English letters.
  • All the characters of jewels are unique.

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach where we compare every stone against every jewel. We iterate through each character in the stones string, and for each stone, we perform another full iteration through the jewels string to check for a match.

Algorithm

  • Initialize a counter jewelCount to 0.
  • Iterate through each character stoneChar in the stones string.
  • For each stoneChar, start a nested loop to iterate through each character jewelChar in the jewels string.
  • If stoneChar is equal to jewelChar, increment jewelCount and break the inner loop.
  • After iterating through all stones, return jewelCount.

Walkthrough

In this method, we use two nested loops. The outer loop iterates over each stone you have, and the inner loop iterates over each type of jewel. For each stone, we check if it matches any of the jewel types. If a match is found, we increment a counter. Since the problem states that all jewel types are unique, we can add a small optimization: once a stone is identified as a jewel, we can stop searching for that particular stone and move on to the next one by breaking the inner loop. Despite this optimization, the fundamental approach remains a pairwise comparison of all stones against all jewels.

class Solution {    public int numJewelsInStones(String jewels, String stones) {        int jewelCount = 0;        for (int i = 0; i < stones.length(); i++) {            char stoneChar = stones.charAt(i);            for (int j = 0; j < jewels.length(); j++) {                char jewelChar = jewels.charAt(j);                if (stoneChar == jewelChar) {                    jewelCount++;                    break; // Jewel types are unique, so we can move to the next stone.                }            }        }        return jewelCount;    }}

Complexity

Time

O(S * J) - Where S is the length of `stones` and J is the length of `jewels`. For each of the S stones, we might have to iterate through all J jewels in the worst case.

Space

O(1) - We only use a few variables to store the count and loop indices, which does not depend on the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space (O(1) space complexity).

Cons

  • Inefficient for large input strings due to its quadratic time complexity.

  • Performs many redundant comparisons if the jewels string is long.

Solutions

class Solution { public int numJewelsInStones ( String jewels , String stones ) { int [] s = new int [ 128 ]; for ( char c : jewels . toCharArray ()) { s [ c ] = 1 ; } int ans = 0 ; for ( char c : stones . toCharArray ()) { ans += s [ c ]; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem