# Count the Number of Special Characters I
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-the-number-of-special-characters-i)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-special-characters-i
**Data structures:** Hash Table, String
---
## Problem
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 <= 50`
* `word` consists of only lowercase and uppercase English letters.

# Approaches
## Brute Force by Iterating Through Alphabet
This approach iterates through each letter of the English alphabet from 'a' to 'z'. For each letter, it checks if both its lowercase and uppercase versions are present in the input string `word` by performing a full scan of the string for each letter.
**Time:** O(26 * N) or simply O(N), where N is the length of the `word`. The outer loop runs a constant 26 times, and for each iteration, the inner loop scans the entire string of length N. · **Space:** O(1), as we only use a few variables to store the count and flags, regardless of the input string's size.
**Pros:** Simple to understand and implement.; Requires no extra space apart from a few variables.
**Cons:** Inefficient as it repeatedly scans the input string for each letter of the alphabet, leading to a higher constant factor in its time complexity compared to single-pass solutions.
### Explanation
The brute-force method systematically checks for each of the 26 possible special characters. It loops from 'a' to 'z', and for each letter, it scans the entire input string `word` to see if both the lowercase and corresponding uppercase forms exist. Two boolean flags, `foundLower` and `foundUpper`, are used within this loop to track their presence. If, after a full scan, both flags are true, a special character has been found, and a counter is incremented. While simple, this method is not optimal because the string is traversed multiple times.

```java
class Solution {
    public int numberOfSpecialChars(String word) {
        int specialCount = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            char upperC = Character.toUpperCase(c);
            boolean foundLower = false;
            boolean foundUpper = false;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) == c) {
                    foundLower = true;
                }
                if (word.charAt(i) == upperC) {
                    foundUpper = true;
                }
            }
            if (foundLower && foundUpper) {
                specialCount++;
            }
        }
        return specialCount;
    }
}
```
### Algorithm
- Initialize a counter `specialCount` to 0.
- Loop through each character `c` from 'a' to 'z'.
- Inside the loop, determine the uppercase equivalent `upperC`.
- Use two boolean flags, `foundLower` and `foundUpper`, initialized to `false`.
- Iterate through the entire `word` to check for the presence of `c` and `upperC`.
- If a character in `word` matches `c`, set `foundLower` to `true`.
- If a character in `word` matches `upperC`, set `foundUpper` to `true`.
- After checking the whole string, if both `foundLower` and `foundUpper` are `true`, it means the character is special, so we increment `specialCount`.
- After the outer loop finishes, `specialCount` will hold the total number of special characters.

## Using Two Hash Sets
This approach improves upon the brute-force method by avoiding repeated traversals of the string. It uses two hash sets to store the unique lowercase and uppercase characters present in the word in a single pass. Then, it checks for matches between the two sets.
**Time:** O(N), where N is the length of the `word`. The first loop to populate the sets takes O(N) time. The second loop runs at most 26 times, and each check is O(1) on average. Thus, the total time is dominated by the initial pass over the string. · **Space:** O(K), where K is the number of unique characters in the alphabet (K=26). Since the alphabet size is fixed, this is considered O(1) constant space.
**Pros:** More efficient than brute force as it only requires a single pass over the input string.; Conceptually clean and easy to reason about.
**Cons:** Has a slight overhead due to using hash sets (hashing, potential collisions) compared to a direct array-based approach.; Uses more space than the brute-force approach, although the space is constant.
### Explanation
To make the process more efficient, we can first collect all unique lowercase and uppercase characters from the `word`. Two hash sets are ideal for this, as they automatically handle uniqueness. We iterate through the `word` once, placing lowercase characters into a `lowerSet` and uppercase characters into an `upperSet`. After this single pass, we have two sets containing all the unique letters of each case. Then, we can iterate through one of the sets (e.g., the `lowerSet`) and for each character, check for the existence of its opposite-case counterpart in the other set. Since hash set lookups take constant time on average, this second step is very fast. This method reduces the overall time complexity by eliminating the need for multiple scans of the input string.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numberOfSpecialChars(String word) {
        Set<Character> lowerSet = new HashSet<>();
        Set<Character> upperSet = new HashSet<>();

        for (char ch : word.toCharArray()) {
            if (Character.isLowerCase(ch)) {
                lowerSet.add(ch);
            } else if (Character.isUpperCase(ch)) {
                upperSet.add(ch);
            }
        }

        int specialCount = 0;
        for (char lowerChar : lowerSet) {
            if (upperSet.contains(Character.toUpperCase(lowerChar))) {
                specialCount++;
            }
        }
        return specialCount;
    }
}
```
### Algorithm
- Create two `HashSet<Character>`: one for lowercase letters (`lowerSet`) and one for uppercase letters (`upperSet`).
- Iterate through the input `word` just once.
- For each character `ch` in the word:
    - If `ch` is a lowercase letter, add it to `lowerSet`.
    - If `ch` is an uppercase letter, add it to `upperSet`.
- After populating the sets, initialize a counter `specialCount` to 0.
- Iterate through `lowerSet`.
- For each lowercase character `lc` in `lowerSet`, check if its uppercase version `Character.toUpperCase(lc)` exists in `upperSet`.
- If the uppercase version is found, increment `specialCount`.
- Finally, return `specialCount`.

## Optimal Approach using Boolean Arrays
This is the most efficient approach. It uses two boolean arrays as direct-addressing tables to track the presence of lowercase and uppercase letters. This avoids the overhead of hashing associated with hash sets and provides the fastest performance.
**Time:** O(N), where N is the length of the `word`. We perform one pass over the string (O(N)) and one pass over the arrays (O(26), which is O(1)). The total time is O(N). · **Space:** O(1). We use two fixed-size arrays of size 26, which is constant space that does not depend on the input size.
**Pros:** Highly efficient with minimal overhead due to direct array access.; Optimal time and space complexity for the given constraints.; Requires only a single pass over the input string.
**Cons:** This approach is specifically tailored to the English alphabet and would need modification for a larger character set.
### Explanation
This optimal solution leverages the fact that the input consists of only English letters. We can use two boolean arrays, `lowerPresent` and `upperPresent`, each of size 26, to act as a checklist for the alphabet. We traverse the input `word` a single time. For each character, we determine if it's lowercase or uppercase and update the corresponding array. For a lowercase character `c`, we mark `lowerPresent[c - 'a']` as `true`. For an uppercase character `C`, we mark `upperPresent[C - 'A']` as `true`. After this O(N) pass, we simply iterate through the 26 indices of the arrays. If `lowerPresent[i]` and `upperPresent[i]` are both `true` for any index `i`, it signifies a special character. This final check takes a constant O(26) time. This method is faster than using hash sets because array indexing is a direct, constant-time operation with no computational overhead for hashing or collision resolution.

```java
class Solution {
    public int numberOfSpecialChars(String word) {
        boolean[] lowerPresent = new boolean[26];
        boolean[] upperPresent = new boolean[26];

        for (char ch : word.toCharArray()) {
            if (ch >= 'a' && ch <= 'z') {
                lowerPresent[ch - 'a'] = true;
            } else if (ch >= 'A' && ch <= 'Z') {
                upperPresent[ch - 'A'] = true;
            }
        }

        int specialCount = 0;
        for (int i = 0; i < 26; i++) {
            if (lowerPresent[i] && upperPresent[i]) {
                specialCount++;
            }
        }
        return specialCount;
    }
}
```
### Algorithm
- Create two boolean arrays of size 26, `lowerPresent` and `upperPresent`, and initialize all their elements to `false`.
- Iterate through the `word` once.
- For each character `ch`:
    - If `ch` is a lowercase letter, calculate its index (`ch - 'a'`) and set `lowerPresent[ch - 'a'] = true`.
    - If `ch` is an uppercase letter, calculate its index (`ch - 'A'`) and set `upperPresent[ch - 'A'] = true`.
- After the pass is complete, initialize a counter `specialCount` to 0.
- Iterate from `i = 0` to `25`.
- For each index `i`, if both `lowerPresent[i]` and `upperPresent[i]` are `true`, increment `specialCount`.
- Return `specialCount`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfSpecialChars(String word) {
    boolean[] s = new boolean['z' + 1];
    for (int i = 0; i < word.length(); ++i) {
      s[word.charAt(i)] = true;
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
      if (s['a' + i] && s['A' + i]) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfSpecialChars(string word) {
    vector<bool> s('z' + 1);
    for (char &c : word) {
      s[c] = true;
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
      ans += s['a' + i] && s['A' + i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSpecialChars(self, word: str) -> int: s = set(word) return sum(a in s and b in s for a, b in zip(ascii_lowercase, ascii_uppercase))

```