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 or 256 flags indexed by character code works as a set with no hashing at all. Mark each jewel letter, then count the stones whose flag is set. Ruby's stones.count(jewels) does the whole job in one call, but the flag array shows what happens underneath.

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.

+12 hidden tests on Submit

Hints

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

0 of 3 opened

Solution

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

Scan the jewels for every stone

Intuition

Take the stones one at a time. For each stone, walk through jewels and stop at the first letter that equals it. A match adds 1 to the count. In the first example the stone u is compared with r and R, finds nothing, and adds nothing.

You can stop at the first match because the jewel letters are all different, so a stone can match at most one of them. A stone that is not a jewel has to be compared with every jewel letter before you know.

With j jewel kinds and s stones that is up to j × s comparisons. Here j ≤ 52, so even 10^4 stones cost about 5 × 10^5 comparisons and the scan finishes in time. The waste shows when the list of kinds grows: 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 question "is this letter a jewel?" has the same answer every time you ask it about the same letter. So answer 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).

The set holds at most 52 letters. In a language without a built-in set, an array of flags indexed by the 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

The algorithm is one loop. Wrong answers come from how the letters are compared and counted.

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; every stone counts, repeats included.
Building the set inside the stone loop. Rebuilding it for every stone costs j steps each time and brings back the O(j × s) of the scan. Build it once, before the loop.
Swapping the arguments. The set must hold jewels, and the loop must walk stones. With the roles reversed, the second example counts the one jewel kind z against the stones and still gets 0, but ("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 the same kind of question, whether its letter is a jewel. A hash set answers that 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 or 256 flags indexed by character code works as a set with no hashing at all. Mark each jewel letter, then count the stones whose flag is set. Ruby's stones.count(jewels) does the whole job in one call, but the flag array shows what happens underneath.

Python

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

Test cases

Case 1

Case 2

Input

jewels = "rR"
stones = "rubyRRr"

Expected