Skip to main content

771. Jewels and Stones

easy

Count how many characters in one string also appear in another. A classic hash-set warm-up that maps cleanly to membership-test fundamentals.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are 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'.

Constraints

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

Examples

Example 1

Input
jewels = "aA", stones = "aAAbbbb"
Output
3

Explanation: Three stones ('a', 'A', 'A') match characters in jewels.

Example 2

Input
jewels = "z", stones = "ZZ"
Output
0

Explanation: Case-sensitive: 'Z' is not in jewels.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A naive nested loop is O(n*m) — fine for the given constraints but worth recognising the inefficiency.

Hint 2

Put the jewels characters into a set, then iterate stones once and increment a counter on membership.

Hint 3

Sets give O(1) average lookup, so the total cost drops to O(n + m).

Solution approach

Reveal approach

Build a set from jewels, then count how many characters in stones are in that set. O(n + m) time where n = len(jewels) and m = len(stones). O(n) extra space for the set. The set is tiny in practice (at most 52 letters), so this is essentially constant memory.

Complexity

Time
O(n + m)
Space
O(n)

Related patterns

  • hash-set
  • counting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Jewels and Stones and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →