# Count the Number of Special Characters II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-special-characters-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-special-characters-ii
**Data structures:** Hash Table, String
---
## Problem
You are given a string `word`. A letter `c` is called **special** if it appears **both** in lowercase and uppercase in `word`, and **every** lowercase occurrence of `c` appears before the **first** uppercase occurrence of `c`.

Return the number of**special** lettersin`word`.

**Example 1:**

**Input:** word = "aaAbcBC"

**Output:** 3

**Explanation:**

The special characters are `'a'`, `'b'`, and `'c'`.

**Example 2:**

**Input:** word = "abc"

**Output:** 0

**Explanation:**

There are no special characters in `word`.

**Example 3:**

**Input:** word = "AbBCab"

**Output:** 0

**Explanation:**

There are no special characters in `word`.

**Constraints:**

* `1 <= word.length <= 2 * 105`
* `word` consists of only lowercase and uppercase English letters.

# Approaches
## Brute-Force Check for Each Character
This approach iterates through all 26 possible special characters ('a' through 'z'). For each character, it scans the entire input string to determine if it meets the special character criteria. The core idea is to verify the condition that the last occurrence of the lowercase letter must appear before the first occurrence of its corresponding uppercase letter.
**Time:** O(26 * N) or O(N), where N is the length of the string. For each of the 26 letters, we scan the string (e.g., `indexOf` and `lastIndexOf` each take O(N) time). · **Space:** O(1), as we only use a few variables to store the count and indices, requiring constant extra space.
**Pros:** The logic is straightforward and directly translates the problem's conditions.; It's easy to implement using built-in string manipulation functions.
**Cons:** This approach repeatedly scans the input string for each of the 26 characters, which is less efficient than a single-pass solution.; For a long string, the total number of operations can be significantly higher than in an optimized approach, even though the Big O notation is the same.
### Explanation
The algorithm checks each of the 26 lowercase English letters one by one. For a letter, say `c`, we need to verify two conditions:
1. Both its lowercase (`c`) and uppercase (`C`) forms exist in the string `word`.
2. Every occurrence of `c` appears before the first occurrence of `C`. This is equivalent to checking if the last occurrence of `c` is before the first occurrence of `C`.

To implement this, for each character from 'a' to 'z':
a. Find the index of the last occurrence of the lowercase letter using `word.lastIndexOf(c)`.
b. Find the index of the first occurrence of the uppercase letter using `word.indexOf(C)`.
c. If both letters are found (indices are not -1) and the last lowercase index is less than the first uppercase index, we count it as a special character.
The total count is returned after checking all 26 letters.

```java
class Solution {
    public int numberOfSpecialChars(String word) {
        int specialCount = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            char upperC = Character.toUpperCase(c);
            
            int lastLower = word.lastIndexOf(c);
            int firstUpper = word.indexOf(upperC);

            if (lastLower != -1 && firstUpper != -1 && lastLower < firstUpper) {
                specialCount++;
            }
        }
        return specialCount;
    }
}
```
### Algorithm
- Initialize a counter `specialCount` to 0.
- Iterate through each character `c` from 'a' to 'z'.
- For each `c`, find the index of its last occurrence in `word`. Let this be `lastLowerIndex`.
- For the same `c`, find the index of the first occurrence of its uppercase version `C`. Let this be `firstUpperIndex`.
- To find these indices, you can either use built-in string functions like `lastIndexOf()` and `indexOf()` or manually iterate through the string.
- Check if both characters were found (i.e., their indices are not -1).
- If both are found and `lastLowerIndex < firstUpperIndex`, it means all lowercase occurrences appear before the first uppercase one. Increment `specialCount`.
- After checking all 26 letters of the alphabet, return `specialCount`.

## Single Pass with Index Tracking Arrays
This approach optimizes the process by scanning the string only once. It uses two arrays to store the first seen index of each uppercase letter and the last seen index of each lowercase letter. By collecting all necessary information in one go, it avoids the redundant scanning of the less efficient method.
**Time:** O(N), where N is the length of `word`. The algorithm involves a single pass through the string and a single pass through the 26-element arrays. · **Space:** O(1), as the two arrays used for tracking indices have a constant size (26), which is independent of the input string's length.
**Pros:** Highly efficient, processing the string in a single pass.; Optimal time complexity for this problem.; Uses constant extra space, making it scalable for large inputs.
**Cons:** Requires careful initialization and handling of indices in the auxiliary arrays.; Uses slightly more memory (though constant) than the brute-force approach.
### Explanation
Instead of rescanning the string for each of the 26 letters, we can gather all the necessary information in a single pass. We need to know two things for each letter `c`: the index of the last occurrence of its lowercase form and the index of the first occurrence of its uppercase form.

We can use two arrays, each of size 26, to store this information:
- `firstUpper[26]` will store the first index of 'A', 'B', ..., 'Z'. Initialize with -1.
- `lastLower[26]` will store the last index of 'a', 'b', ..., 'z'. Initialize with -1.

We iterate through the input string `word` once:
- If we encounter a lowercase character `c` at index `i`, we update `lastLower[c - 'a'] = i`. This ensures `lastLower` always holds the index of the most recently seen occurrence.
- If we encounter an uppercase character `C` at index `i`, we check if `firstUpper[C - 'A']` is still -1. If it is, we set `firstUpper[C - 'A'] = i`. This ensures we only record the index of its very first occurrence.

After this single pass, we iterate from 0 to 25. For each letter, we check if `lastLower[i]` and `firstUpper[i]` are valid (not -1) and if `lastLower[i] < firstUpper[i]`. If so, we increment our special character count.

```java
class Solution {
    public int numberOfSpecialChars(String word) {
        int[] lastLower = new int[26];
        int[] firstUpper = new int[26];
        java.util.Arrays.fill(lastLower, -1);
        java.util.Arrays.fill(firstUpper, -1);

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (Character.isLowerCase(c)) {
                lastLower[c - 'a'] = i;
            } else {
                int index = c - 'A';
                if (firstUpper[index] == -1) {
                    firstUpper[index] = i;
                }
            }
        }

        int specialCount = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) {
                specialCount++;
            }
        }
        return specialCount;
    }
}
```
### Algorithm
- Initialize two integer arrays, `lastLower` and `firstUpper`, both of size 26, and fill them with -1. These will store the last index of a lowercase letter and the first index of an uppercase letter, respectively.
- Iterate through the input string `word` with index `i` from 0 to `word.length() - 1`.
- For each character `c` at index `i`:
  - If `c` is a lowercase letter, update `lastLower[c - 'a'] = i`.
  - If `c` is an uppercase letter, check if `firstUpper[c - 'A']` is still -1. If it is, this is the first time we've seen this uppercase letter, so set `firstUpper[c - 'A'] = i`.
- After iterating through the string, initialize a counter `specialCount` to 0.
- Iterate from `i = 0` to 25.
- For each `i`, check if the character is special: `lastLower[i] != -1`, `firstUpper[i] != -1`, and `lastLower[i] < firstUpper[i]`.
- If all conditions are met, increment `specialCount`.
- Return `specialCount`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int numberOfSpecialChars(string word) {
    vector<int> first('z' + 1);
    vector<int> last('z' + 1);
    for (int i = 1; i <= word.size(); ++i) {
      int j = word[i - 1];
      if (first[j] == 0) {
        first[j] = i;
      }
      last[j] = i;
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
      if (last['a' + i] && first['A' + i] && last['a' + i] < first['A' + i]) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSpecialChars(self, word: str) -> int: first, last = {}, {} for i, c in enumerate(word): if c not in first: first[c] = i last[c] = i return sum(a in last and b in first and last[a] < first[b] for a, b in zip(ascii_lowercase, ascii_uppercase))

```