The O(n) Club: Jewels and Stones — HashSet Heroics for the Chronically Loopy

The O(n) Club: Jewels and Stones — HashSet Heroics for the Chronically Loopy

⚡ TL;DR

You have a string of jewels (unique, case-sensitive, probably the main character) and a string of stones (the extras). Count how many stones are actually jewels. Old-school brute force is O(n × m) and makes your CPU contemplate retirement:

// Painful O(n × m) way
int count = 0;
for (char stone : stones.toCharArray()) {
  for (char jewel : jewels.toCharArray()) {
    if (stone == jewel) count++;
  }
}
return count;

🧠 How Devs Usually Mess This Up

Let’s be honest—most folks reach for the double-for like it’s a favorite hoodie: check every stone against every jewel, line by line, character by character, as if brute effort ever charmed an interviewer. Or they waste time deduplicating jewels, ignoring the problem statement (which basically shouts “They’re unique!”). And let’s not forget ignoring case sensitivity—because apparently ‘a’ and ‘A’ are always twins, right?

🔍 What’s Actually Going On

Picture this: The jewels string is a velvet VIP guestlist, and stones are the masses at the club’s rope. Your job? For every stone, check if it’s on the VIP list—a hash set of jewels. Forget the bouncer making phone calls for every guest; hand him an iPad with instant search. Use a HashSet for O(1) lookups and quit the O(n²) nightlife drama.

🛠️ PseudoCode

• Create a HashSet: Set<Character> jewelSet = new HashSet<>() — so every jewel gets fast-tracked.
• Loop through stones: For each stone, if jewelSet.contains(stone), ring the cash register (count++), otherwise keep walking.
• Return the count: That’s the full VIP attendance—no lookups, no drama.

💻 The Code

public int numJewelsInStones(String jewels, String stones) {
    Set<Character> jewelSet = new HashSet<>();
    for (char c : jewels.toCharArray()) {
        jewelSet.add(c);
    }
    int count = 0;
    for (char s : stones.toCharArray()) {
        if (jewelSet.contains(s)) {
            count++;
        }
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Case sensitivity matters: ‘a’ ≠ ‘A’. One’s a jewel, one’s an impostor. Don’t mix them up.
• No need to deduplicate jewels: They’re already unique (seriously, read the prompt).
• Avoid the double-loop of doom: Unless you want your code reviewer to age ten years before your eyes.
• Time/Space costs: O(m + n) time, O(m) space (where m = jewels length), and your CPU will thank you.
• Edge alert: Empty jewels or stones? The answer’s 0. Even a philosopher can’t debate that.

🧠 Interviewer Brain-Tattoo

“If your problem smells like a club guestlist, let a HashSet do the velvet-rope magic—not ten thousand awkward introductions.”