Description

You’re 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".

Example 1:

1Input: jewels = "aA", stones = "aAAbbbb"
2Output: 3

Example 2:

1Input: jewels = "z", stones = "ZZ"
2Output: 0

Constraints:

  • 1 <= jewels.length, stones.length <= 50
  • jewels and stones consist of only English letters.
  • All the characters of jewels are unique.

Solution

Brute Force

The brute force approach for this will be to iterate through each character of stones and verify if there exists matching character in jewels. If yes, then we simply increment the count.

 1class Solution {
 2    public int numJewelsInStonesBrute(String jewels, String stones) {
 3        int count = 0;
 4        for (char c: stones.toCharArray()) {
 5            if (jewels.indexOf(c) != -1) {
 6                count++;
 7            }
 8        }
 9        return count;
10    }
11}

This solution even though works is suboptimal.

  • Time Complexity: O(m * n) where m = length of stones and n = length of jewels. indexOf() function also takes linear time.
  • Space Complexity: O(1)

Using Array

We can use array to keep track of which characters occur in jewels. Next time, when iterating over stones, we just have to check in this array to make sure that character was present in the jewels. If it was present, we increment the count by 1. In order to save space, we can store 52 English characters in their respective position. So, the operation becomes little more complicated than usual. Alternatively, we could create an array of size 123 to cover both uppercase English characters (index position 65 to 90) and lowercase English character (index position 97 to 122).

 1class Solution {
 2    public int numJewelsInStones(String jewels, String stones) {
 3        int count = 0;
 4        int[] map = new int[52];
 5        for (char c: jewels.toCharArray()) {
 6            if (Character.isUpperCase(c)) {
 7                map[c - 'A'] = 1;
 8            } else {
 9                map[c - 'a' + 26] = 1;
10            }
11        }
12        for (char c: stones.toCharArray()) {
13            if (Character.isUpperCase(c) && map[c - 'A'] == 1) {
14                count++;
15            } else if (Character.isLowerCase(c) && map[c - 'a' + 26] == 1) {
16                count++;
17            }
18        }
19        return count;
20    }
21}
  • Time Complexity: O(m + n), where m = length of stones and n = length of jewels
  • Space Complexity: O(1) - constant space because the size of the map is fixed

Using Hashing

In this approach, we can store the jewels characters in HashSet or HashMap and when iterating through stones, we check if we have seen this character in jewels string. If yes, increment the count.

 1class Solution {
 2    public int numJewelsInStones (String jewels, String stones) {
 3        int count = 0;
 4        Set<Character> set = new HashSet<>();
 5        for (char c: jewels.toCharArray()) {
 6            set.add(c);
 7        }
 8        for (char c: stones.toCharArray()) {
 9            if (set.contains(c)) {
10                count++;
11            }
12        }
13        return count;
14    }
15}
  • Time Complexity: O(m + n), where m = length of stones and n = length of jewels
  • Space Complexity: O(n) - linear space because the size of the set is proportional to the number of jewels