Jewels and Stones

Q: What is the time complexity of Jewels and Stones?

With a set it is O(j + s) : j steps to build the set from jewels and one constant-time lookup for each of the s stones. Scanning jewels for every stone is O(j × s) .

Q: Can you solve it without a set?

Yes. The letters are English letters, so an array of 128 flags indexed by character code works as a set with no hashing. Mark each jewel letter, then count the stones whose flag is set.

BeginnerHashing

+10

You get two strings of letters. Each letter in jewels names one kind of jewel, and no letter repeats. Each letter in stones is one stone you own. Return how many of your stones are jewels. Letters are case-sensitive: "a" and "A" are different kinds.

Function

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: the kinds of stones that count as jewels, one letter each
stonesstring: the stones you own, one letter each
Returnsinteger: the number of stones whose letter appears in jewels

Constraints

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Both strings contain only English letters, lowercase and uppercase.
The letters of jewels are all different.

Examples

Input: jewels = "rR"stones = "rubyRRr"
Output: 4
Explanation: The jewel kinds are r and R. In rubyRRr the stones r, R, R and r match, while u, b and y do not, so the answer is 4.

Input: jewels = "z"stones = "ZZZ"
Output: 0
Explanation: The only jewel kind is lowercase z. Every stone is an uppercase Z, a different kind, so none of them counts.

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

For every stone you ask one question: is this letter a jewel? Searching the jewels string for each stone repeats the same scan. Put the jewel letters in a set once, and every stone becomes a single lookup.

Scan the jewels for every stone

Intuition

For each stone, walk through jewels and stop at the first equal letter; a match adds 1 to the count. Stopping there is safe because the jewel letters are all different, so a stone matches at most one of them. In the first example the stone u is compared with r and R and adds nothing.

With j jewel kinds and s stones that is up to j × s comparisons. Since j ≤ 52, 10^4 stones cost about 5 × 10^5 comparisons, which is fast here. The cost grows with the number of kinds, because the same search runs again for every stone.

Algorithm

Set count to 0.
For each stone, compare it with each letter of jewels.
On the first equal letter, add 1 to count and move on to the next stone.
Return count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Put the jewels in a set

Intuition

The answer to "is this letter a jewel?" never changes for a given letter, so compute it once per kind: build a set from the letters of jewels. A set answers membership in constant time, so each stone costs one lookup instead of a scan.

For the first example the set is {r, R}. Walking rubyRRr, the lookups say yes, no, no, no, yes, yes, yes: four jewels. Building the set takes j steps and the walk takes s, so the total is O(j + s). In a language without a built-in set, an array of flags indexed by character code does the same job.

Algorithm

Build a set containing every letter of jewels.
Set count to 0.
For each stone, add 1 to count if the set contains it.
Return count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Pitfalls and edge cases

Ignoring case. Lowercasing both strings makes z match Z, and the second example returns 3 instead of 0.
Counting distinct jewel kinds instead of stones. rubyRRr holds two kinds of jewel but four jewel stones; repeats count.
Building the set inside the stone loop. That costs j steps per stone and brings back O(j × s).
Swapping the arguments. The set must hold jewels and the loop must walk stones. Reversed, ("a", "aaa") returns 1 instead of 3.

Frequently asked questions3

What is the time complexity of Jewels and Stones?

With a set it is O(j + s): j steps to build the set from jewels and one constant-time lookup for each of the s stones. Scanning jewels for every stone is O(j × s).

Why use a hash set for Jewels and Stones?

Every stone asks whether its letter is a jewel. A hash set answers in constant time, while searching the jewels string takes time proportional to its length. You pay once to build the set and save on every stone after that.

Can you solve it without a set?

Yes. The letters are English letters, so an array of 128 flags indexed by character code works as a set with no hashing. Mark each jewel letter, then count the stones whose flag is set.

def numJewelsInStones(jewels, stones):
    # Write code here

Test #1

Test #2

Arguments

jewels = "rR"
stones = "rubyRRr"

Expected Output