LeetCode "Jewels and Stones": counting certain characters in a string

Question

LeetCode "Jewels and Stones"

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50. The characters in J are distinct.

My approach:

class Solution {
    public int numJewelsInStones(String J, String S) {

        int count = 0;
        for( int i = 0; i < J.length(); i++ )
        {
            for( int j = 0; j < S.length(); j++ )
            {
                if( J.charAt(i) == S.charAt(j) )
                    count++;
            }
        }
        return count;
    }
}

Time complexity: O(n^2)

Space complexity: O(1)

Another approach:

class Solution {
    public int numJewelsInStones(String J, String S) {
        Set<Character> jSet = new HashSet<>();
        for(Character ch : J.toCharArray()) {
            jSet.add(ch);
        }
        int count = 0;
        for(Character ch: S.toCharArray()) {
            if(jSet.contains(ch)) {
                count++;
            }
        }
        return count;
    }
}

Time complexity: O(n) Space complexity: O(n)

I have the following questions regarding the above code snippets:

1. Which approach is better according to you?

2. Will the interviewer be more impressed by the 2nd method as it has used Set?

3. How can I further improve my code (sort the string and perform a binary search)-> O(n*log(n))?

Answer 1

Caution — naïve application of big-O analysis will lead you astray here!

First of all, you should be more precise about what you mean by "n". In this problem, there are |J| and |S|: the lengths of J and S. Your first approach is O(|J| |S|); your second one is O(|J| + |S|).

More importantly, big-O analysis only tells you how well an algorithm scales to handle large inputs. In this challenge, though, |J| and |S| are at most 50 — very small inputs, by computer standards. That means that the constant factors, which are disregarded in big-O analysis, actually matter. (Another way to look at it: with those limits, |J| and |S| are both O(1), so any sane solution is also O(1)!)

Consider how much code is involved in making a HashSet. A HashSet is actually a disguise for a HashMap. A HashMap is implemented as an array of trees, each containing Map.Entry objects. The array should be optimally sized to hold all the characters of J with no hashcode collisions, but you neglected to specify size hints when calling the HashSet<>() constructor. Then, you have to insert each character of J, which involves boxing a char into a Character, calculating its hashcode, making a Map.Entry for it, and inserting it into the HashMap's table. The problem is, Java makes it easy to execute a lot of operations without making you aware of how much work it actually is!

Since the challenge states that all characters are letters — which I interpret to mean the 52 letters in the English alphabet, you could achieve an efficient test of membership in J using a simple lookup table:

public int numJewelsInStones(String j, String s) {
    boolean[] jewels = new boolean[128];
    for (int i = 0; i < j.length(); i++) {
        jewels[j.codePointAt(i)] = true;
    }
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (jewels[s.codePointAt(i)]) {
            count++;
        }
    }
    return count;
}

Answer 2

Not much time, so just in short:

1. Definitely the second. It shows that you have got at least a general grip on datastructures (knowing the complexity of HashSet operations) and know a bit about the standard library. Regarding the fist one: this even uses a loop instead of indexOf - I'd immediatly show you to the door for that, if I were the interviewer...
2. Second is definitely better, but not impressive eiher. Try getting a grip on the stream API and play around with String.codePoints - my own try-that-for-comparison-solution was 2 lines using this...
3. You shouldn't. From my opinion, it is OK to explain in addition that there might be a possible solution using binary search over the stones string, which completes in \$O(n\times log(n))\$, but I would not to see an even longer solution for micro-optimizing a simple problem which takes milliseconds to execute. Simplicity, readability and clarity are the key attributes.

Answer 3

You could speed up the first version by switching the loops, so that the loop over J becomes the inner loop, and short-circuiting the loop over J, because once you have found a character in J that matches the current character in S, you don't have to loop over the remaining characters of J (mtj's suggestion to use String.indexOf(char) would amount to this).

As for the second approach: Why do you first convert the strings to a char[] before iterating over their characters? You did not do this in the first version, so what do you gain from it by doing it in the second version?

About your question which approach is better: Depends on what you mean by better. I think both versions are quite straighforward and to the point. For large strings, the second version might be preferable because it has a lower time complexity. However, you write that the strings will contain at most 50 characters, so the benefit of constant-time lookup might not outweigh the cost of creating a Set and implicitly converting each primitive char to a Character object. But this is just a guess, I did not measure it.

Answer 4

public long numJewelsInStones(String J, String S) {
    Set<Character> jewels = J.chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
    return jewels.stream().filter(x -> S.contains(x + "")).count();
}

Definitely, second approach is better, java 8 can actually truncate it further. Also jewels is a better name than jSet.