Jewels and Stones
Easy · Arrays & Hashing · Hash Table · String
Problem
You are given a string jewels listing the types of stones that are jewels, and a string stones listing the stones you own, one letter per stone.
Return how many of your stones are also jewels. Letters are case-sensitive, so "a" and "A" are different types. Every letter in jewels is unique.
Examples
Input: jewels = "xZ", stones = "xxzZq" Output: 3
Two "x" and one "Z" are jewels; the lowercase "z" and the "q" are not.
Input: jewels = "k", stones = "mmm" Output: 0
None of the stones is a "k".
Input: jewels = "ab", stones = "abba" Output: 4
All four stones are an "a" or a "b".
Constraints
- 1 <= len(jewels), len(stones) <= 50
- jewels and stones consist of English letters only
- All letters of jewels are unique
Approaches
- Baseline: search the jewels for every stone — time O(j · s), space O(1)
Follow-up
If the jewel types were whole words rather than single letters, the same set works with strings as keys. See the use cases for counting each jewel type separately, and for accepting a word only when all of its letters are allowed.
Related problems
Start free on Cariara · Coding problems · System design studio
