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 Sam K., 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

More Strings practice problems

See all Strings problems →