algoadvance

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:

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

---

Clarifying Questions:

1. Are the strings jewels and stones always non-empty?
   • Yes, for the sake of this problem, you can assume they are non-empty.
2. Do the strings contain only alphabetic characters?
   • Yes, both jewels and stones contain only alphabetic characters and are case-sensitive.
3. Can there be duplicate characters in the jewels string?
   • No, the jewels string contains unique characters.

---

Strategy:

1. Set Conversion for Jewels: Convert the jewels string into a set for O(1) average-time complexity lookups.
2. Count Matching Stones: Iterate through each character in stones and count how many of these characters are present in the jewels set.

Code:

def numJewelsInStones(jewels: str, stones: str) -> int:
    jewels_set = set(jewels)  # Step 1: Convert 'jewels' to a set
    count = 0
    
    for stone in stones:  # Step 2: Iterate through 'stones'
        if stone in jewels_set:
            count += 1
    
    return count

Time Complexity:

• Conversion to set: O(J), where J is the length of the jewels string.
• Iteration through stones: O(S), where S is the length of the stones string.
• Total Time Complexity: O(J + S), which is efficient given that set lookups are O(1) on average.

Explanation with Example:

For the input jewels = "aA" and stones = "aAAbbbb"

• Convert jewels to a set: {'a', 'A'}
• Iterate through the stones: count how many times characters ‘a’ and ‘A’ appear in stones.
• The characters ‘a’ and ‘A’ appear 3 times in total, hence the output is 3.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?