Jewels and Stones - Practice Coding Problems

Jewels and Stones - Problem

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".

Input & Output

Example 1 — Basic Case

$ Input: jewels = "aA", stones = "aAAbbbb"

› Output: 3

💡 Note: The stones 'a', 'A', and 'A' match jewel types in "aA". The letter 'b' is not a jewel type.

Example 2 — Case Sensitivity

$ Input: jewels = "z", stones = "ZZ"

› Output: 0

💡 Note: Since letters are case sensitive, lowercase 'z' is different from uppercase 'Z'. No matches found.

Example 3 — All Match

$ Input: jewels = "abc", stones = "aabbcc"

› Output: 6

💡 Note: All stones match jewel types: 'a'(2), 'b'(2), 'c'(2) = 6 total jewels.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Jewels: "aA", Stones: "aAAbbbb"

Process

Check each stone against jewel types

Output

Count of matching stones: 3

Key Takeaway

🎯 Key Insight: Use a hash set to store jewel types for O(1) lookup time per stone

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use a hash set for O(1) jewel type lookups instead of scanning the jewels string repeatedly. Best approach is hash set lookup with Time: O(n+m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Lookup	O(n+m)	O(m)	Store jewel types in a hash set for O(1) lookup per stone
Brute Force	O(n×m)	O(1)	For each stone, check if it matches any jewel type

Hash Set Lookup — Algorithm Steps

Create hash set from jewels string
Iterate through each stone
Check if stone exists in hash set, increment counter if found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Store all jewel types {a, A} in hash set

Check Each Stone

For each stone, check if it exists in set

Count Matches

Increment counter for each match found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int solution(char* jewels, char* stones) {
    bool jewelSet[256] = {false}; // ASCII table size
    
    // Build jewel set
    int jewels_len = strlen(jewels);
    for (int i = 0; i < jewels_len; i++) {
        jewelSet[(unsigned char)jewels[i]] = true;
    }
    
    // Count stones that are jewels
    int count = 0;
    int stones_len = strlen(stones);
    for (int i = 0; i < stones_len; i++) {
        if (jewelSet[(unsigned char)stones[i]]) {
            count++;
        }
    }
    return count;
}

int main() {
    char jewels[100], stones[100];
    fgets(jewels, sizeof(jewels), stdin);
    fgets(stones, sizeof(stones), stdin);
    jewels[strcspn(jewels, "\n")] = 0;
    stones[strcspn(stones, "\n")] = 0;
    int result = solution(jewels, stones);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n+m)

O(m) to build hash set, O(n) to check each stone

✓ Linear Growth

Space Complexity

O(m)

Hash set stores up to m unique jewel types

✓ Linear Space

95.0K Views

High Frequency

~8 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Lookup — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler