The problem
Given jewel types and a bag of stones, count how many stones are jewels. Letters are case-sensitive.
Input: jewels "aA", stones "aAAbbbb" Output: 3
Picture it
Picture sorting a miner’s bag. Put the jewel types in a set, then check each stone against the set in one step.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Set membership per stone. O(j + s).
Python solution
def num_jewels(jewels, stones):
kinds = set(jewels)
count = 0
for s in stones:
if s in kinds:
count += 1
return countIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.