LeetCode "Jewels and Stones": counting certain characters in a string
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&lt;&gt;() 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 &lt; j.length(); i++) {
        jewels[j.codePointAt(i)] = true;
    }
    int count = 0;
    for (int i = 0; i &lt; s.length(); i++) {
        if (jewels[s.codePointAt(i)]) {
            count++;
        }
    }
    return count;
}