Count the Number of Special Characters I - Solution & Explanation

Problem Overview: You are given a string containing uppercase and lowercase English letters. A character is considered special if both its lowercase and uppercase versions appear somewhere in the string. The goal is to count how many such characters exist.

Approach 1: Using Sets (O(n) time, O(1) space)

This approach relies on hash-based lookup using two sets. Iterate through the string once and store lowercase characters in one set and uppercase characters in another. After the scan, check each lowercase character and verify whether its uppercase equivalent exists in the uppercase set using constant-time membership checks. The key insight is that sets provide O(1) average lookup, which keeps the solution linear even when checking character pairs. Since the English alphabet is fixed (26 letters), the space usage is effectively constant.

This method is simple to implement and very readable. If you're solving problems involving presence checks or deduplication in a string, a set-based approach is usually the quickest way to reach an optimal solution.

Approach 2: Direct Indexing with Boolean Arrays (O(n) time, O(1) space)

This approach replaces sets with two boolean arrays of size 26. One array tracks whether a lowercase letter a–z appears, and the other tracks whether an uppercase letter A–Z appears. While iterating through the string, convert each character to an index using simple arithmetic (for example, c - 'a' or c - 'A') and mark the corresponding position in the array.

After processing the entire string, iterate from index 0 to 25 and count how many indices are marked in both arrays. Each shared index represents a character whose lowercase and uppercase forms are present. This technique uses direct indexing instead of hashing, which removes hash overhead and guarantees constant-time operations.

This approach is common in problems involving frequency tracking or character presence because arrays are extremely cache-friendly and predictable. It fits naturally when the character domain is small and fixed, such as the English alphabet.

Recommended for interviews: Interviewers generally expect an O(n) solution using either sets or fixed-size arrays. The set-based solution clearly demonstrates understanding of hash lookups, while the boolean array approach shows deeper awareness of constraints and constant-space optimization. Writing the set version first is often fastest during interviews, then mentioning the array optimization shows strong problem-solving depth.