Count Letters with Ordered Lowercase and Uppercase Occurrences
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Letters with Ordered Lowercase and Uppercase Occurrences
You are given a string `word` containing lowercase and uppercase English letters.
A letter is **special** when both of these conditions hold:
- Its lowercase and uppercase forms both occur in `word`.
- Every occurrence of its lowercase form is before the first occurrence of its uppercase form.
Return the number of special letters. Count each letter once, regardless of how often it occurs.
### Examples
**Example 1**
```text
Input: word = "bbBaaACCcD"
Output: 2
```
The letters `b` and `a` qualify. The lowercase `c` occurs after an uppercase `C`, so `c` does not qualify. The letter `d` has no lowercase occurrence.
**Example 2**
```text
Input: word = "aABbCc"
Output: 1
```
Only `a` qualifies. For both `b` and `c`, an uppercase occurrence precedes a lowercase occurrence.
### Constraints
- `1 <= word.length <= 2 * 10^5`.
- `word` consists only of lowercase and uppercase English letters.
### Clarifying Questions
- Does one lowercase occurrence before an uppercase occurrence suffice? No; every lowercase occurrence of that letter must precede its first uppercase occurrence.
- Can a letter that appears in only one case qualify? No.
- Do repeated uppercase occurrences disqualify a letter? No, provided every lowercase occurrence is before the first uppercase one.
- Are we counting distinct letters or occurrences? Distinct letters.
### C++ Interface
```cpp
class Solution {
public:
int numberOfSpecialChars(string word) {
}
};
```
### Reasoning Checkpoints
- Apply both the presence requirement and the ordering requirement to each letter.
- Handle repeated occurrences and mixed ordering without counting a letter more than once.
- Justify the result and resource use for strings of the maximum allowed length.
```hint Compare the boundary occurrences
For each letter, compare its last lowercase position with its first uppercase position. Keep a separate indication that each form actually occurs.
```
Overview: Given a mixed-case English string, count letters whose lowercase occurrences all precede their first uppercase occurrence. Includes repeated-letter examples and the original C++ interface.