Count the Number of Special Characters I

Count the Number of Special Characters I

What is this problem about?

The Count the Number of Special Characters I coding problem asks you to count how many "special" characters exist in a string. A character is considered special if both its lowercase and uppercase versions appear at least once in the given string.

For example, in "abAb", 'a' is special (both 'a' and 'A' exist) and 'b' is special (both 'b' and 'B' exist).

Why is this asked in interviews?

This is a standard "Easy" problem used by Amazon and Google to test basic hash table interview pattern or frequency counting skills. It evaluates if a candidate can correctly map characters to their counterparts and avoid double-counting. It also checks for clean string processing and set manipulation.

Algorithmic pattern used

This problem uses Frequency Counting (Hash Set).

1. Use two Hash Sets (or boolean arrays of size 26): lower_seen and upper_seen.
2. Iterate through the string once.
3. If a character is lowercase, add it to lower_seen.
4. If a character is uppercase, add it to upper_seen.
5. Iterate through the 26 possible letters. If a letter c exists in both lower_seen and upper_seen, increment the result.

Example explanation

s = "aaAbc"

1. Set lower: {a, b, c}
2. Set upper: {A}
3. Check letters:
   • 'a': 'a' in lower, 'A' in upper. (Special!)
   • 'b': 'b' in lower, 'B' NOT in upper.
   • 'c': 'c' in lower, 'C' NOT in upper. Total = 1.

Common mistakes candidates make

• Case conversion: Forgetting how to correctly convert between cases (e.g., using char - 'a' for index 0-25).
• Double counting: Counting 'a' and 'A' as two separate special letters instead of one pair.
• Efficiency: Using nested loops ($O(N^2)$) to check for counterparts instead of a single pass with sets ($O(N)$).

Interview preparation tip

For character counting, always ask yourself if the input is ASCII or Unicode. If it's just English letters, a fixed-size array bool[26] is often more efficient and cleaner than a Set or Map.