You are given a string word. A letter is called special if it appears both in lowercase and uppercase in word.
Return the number of special letters in word.
Example 1:
Input: word = "aaAbcBC"
Output: 3
Explanation:
The special characters in word are 'a', 'b', and 'c'.
Example 2:
Input: word = "abc"
Output: 0
Explanation:
No character in word appears in uppercase.
Example 3:
Input: word = "abBCab"
Output: 1
Explanation:
The only special character in word is 'b'.
Constraints:
1 <= word.length <= 50word consists of only lowercase and uppercase English letters.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.
This approach involves using two sets to track lowercase and uppercase appearances of each character. As you iterate over the string, add lowercase characters to one set and uppercase characters to another. After processing the string, check which lowercase characters have their uppercase counterparts present in the sets.
The solution uses two integer arrays of size 26 to track lowercase and uppercase letters found in the input string. By iterating through the string, we fill these arrays. Finally, we check corresponding positions in both arrays to count the number of special characters.
Time Complexity: O(n) where n is the length of the string, as each character is processed once.
Space Complexity: O(1), since we use fixed size arrays for tracking lowercase and uppercase letters.
This approach involves using two boolean arrays to directly track all lowercase and uppercase letters. This avoids set operations and provides constant time complexity checking.
This implementation uses two boolean arrays to get constant-time access to check if any letter has both lower and uppercase forms in the input string.
Time Complexity: O(n), iterating once over the string.
Space Complexity: O(1), with fixed-size boolean arrays.
We use a hash table or array s to record the characters that appear in the string word. Then we traverse the 26 letters. If both the lowercase and uppercase letters appear in s, the count of special characters is incremented by one.
Finally, return the count of special characters.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Where n is the length of the string word, and |\Sigma| is the size of the character set. In this problem, |\Sigma| leq 128.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Sets | Time Complexity: O(n) where n is the length of the string, as each character is processed once. |
| Approach 2: Direct Indexing with Boolean Arrays | Time Complexity: O(n), iterating once over the string. |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Sets | O(n) | O(1) | Best general approach when using hash-based membership checks for characters |
| Direct Indexing with Boolean Arrays | O(n) | O(1) | When the character range is fixed (a–z, A–Z) and you want the most lightweight implementation |
3121 & 3120 Count the Number of Special Characters II & Characters I • Aryan Mittal • 2,918 views views
Watch 9 more video solutions →Practice Count the Number of Special Characters I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor