Count the Number of Special Characters I

Difficulty: Easy | Acceptance: 67.00% | Paid: No Topics: Hash Table, String

You are given a string word.

A character is special if it appears in both lowercase and uppercase forms in word.

Return the number of special characters in word.

Table of Contents

• Examples
• Constraints
• Hash Set Approach
• Boolean Array Approach
• Bitmasking Approach

Examples

Example 1

Input: word = "aaAbcBC"
Output: 2
Explanation:
The special characters are 'a' and 'b'.

Example 2

Input: word = "abc"
Output: 0
Explanation:
No character appears in both lowercase and uppercase form.

Example 3

Input: word = "abBCab"
Output: 1
Explanation:
The special character is 'b'.

Constraints

1 <= word.length <= 50
word consists of lowercase and uppercase English letters.

Hash Set Approach

Intuition We can use two sets to store the unique lowercase and uppercase characters found in the string. By iterating through the alphabet, we can check if a character exists in both sets.

Steps

• Initialize two empty sets, one for lowercase and one for uppercase.
• Iterate through each character in the input string.
• If the character is lowercase, add it to the lowercase set. If it is uppercase, add it to the uppercase set.
• Initialize a counter to 0.
• Iterate from ‘a’ to ‘z’ (or 0 to 25).
• For each letter, check if it exists in the lowercase set and if its uppercase version exists in the uppercase set.
• If both exist, increment the counter.
• Return the counter.

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        lower_set = set()
        upper_set = set()
        
        for char in word:
            if 'a' <= char <= 'z':
                lower_set.add(char)
            else:
                upper_set.add(char)
        
        count = 0
        for i in range(26):
            char = chr(ord('a') + i)
            if char in lower_set and char.upper() in upper_set:
                count += 1
                
        return count

Complexity

• Time: O(N)
• Space: O(1)
• Notes: The space is O(1) because the sets can hold at most 26 characters each, regardless of the input size N.

Boolean Array Approach

Intuition Since we only deal with English letters, we can use two fixed-size boolean arrays of length 26 to track the presence of lowercase and uppercase characters. This is often faster than using hash sets due to direct indexing.

Steps

• Create two boolean arrays of size 26, initialized to false.
• Iterate through the string. For each character, determine its index (0 for ‘a’ or ‘A’, 25 for ‘z’ or ‘Z’).
• Mark the corresponding position in the lowercase or uppercase array as true.
• Iterate from 0 to 25. If both the lowercase and uppercase arrays have true at the current index, increment the result.
• Return the result.

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        lower = [False] * 26
        upper = [False] * 26
        
        for char in word:
            if 'a' <= char <= 'z':
                lower[ord(char) - ord('a')] = True
            else:
                upper[ord(char) - ord('A')] = True
                
        count = 0
        for i in range(26):
            if lower[i] and upper[i]:
                count += 1
                
        return count

Complexity

• Time: O(N)
• Space: O(1)
• Notes: Uses fixed-size arrays (52 booleans total), which is very memory efficient.

Bitmasking Approach

Intuition We can use two integers as bitmasks to represent the presence of characters. Each bit in an integer corresponds to a letter in the alphabet (e.g., bit 0 for ‘a’/‘A’, bit 1 for ‘b’/‘B’). This allows us to store the state of all 26 letters in a single 32-bit integer.

Steps

• Initialize two integers, lowerMask and upperMask, to 0.
• Iterate through the string.
• If the character is lowercase, calculate its bit position and set the corresponding bit in lowerMask using bitwise OR.
• If the character is uppercase, calculate its bit position and set the corresponding bit in upperMask.
• After processing the string, iterate from 0 to 25.
• For each index i, check if the i-th bit is set in both lowerMask and upperMask using bitwise AND.
• If both bits are set, increment the counter.
• Return the counter.

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        lower_mask = 0
        upper_mask = 0
        
        for char in word:
            if 'a' <= char <= 'z':
                lower_mask |= 1 << (ord(char) - ord('a'))
            else:
                upper_mask |= 1 << (ord(char) - ord('A'))
                
        count = 0
        for i in range(26):
            if (lower_mask >> i) & 1 and (upper_mask >> i) & 1:
                count += 1
                
        return count

Complexity

• Time: O(N)
• Space: O(1)
• Notes: Extremely space-efficient, using only two integers to store the entire state.