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 letters in 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 * 105word 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 in the string, and every lowercase occurrence appears before the first uppercase occurrence. The task is to count how many characters satisfy this rule.
Approach 1: Using HashMaps to Track First Occurrence (O(n) time, O(1) space)
This approach scans the string while storing positional information for each character using hash maps. Track the last index where each lowercase letter appears and the first index where each uppercase letter appears. After building these maps, iterate through all 26 letters and check whether both versions exist. A character is special if the last lowercase index is strictly less than the first uppercase index. Hash lookups make each check constant time, so the full solution runs in O(n) time with O(1) extra space because the alphabet size is fixed.
This method is flexible and easy to implement in languages with strong dictionary support. It fits naturally with problems involving character tracking using a hash table and sequential scans of a string.
Approach 2: Two-Pass Array Approach (O(n) time, O(1) space)
This approach replaces hash maps with fixed-size arrays of length 26. During the first pass, record the last index of every lowercase letter and the first index of every uppercase letter. Arrays work well here because the problem only deals with English letters. In the second pass (or a simple loop over 26 characters), check the same ordering condition: lastLower[i] < firstUpper[i].
Arrays eliminate hashing overhead and are slightly faster in practice. Each character is processed once, producing O(n) time complexity with constant O(1) space. This version is common in C, C++, and C# implementations where direct indexing is faster than dictionary operations. The logic still relies on basic string traversal and index comparison.
Recommended for interviews: Interviewers usually expect the linear-time solution that records positions of lowercase and uppercase characters. The hash map version demonstrates clear reasoning about character tracking, while the array version shows optimization awareness and better constant factors. Both achieve O(n) time and constant space, which is the optimal complexity for this problem.
This approach involves using hashmaps (dictionaries in Python) to keep track of the first occurrence of each lowercase letter and whether an uppercase version of it has already been seen. If a lowercase letter is seen before its uppercase counterpart, it is counted as special.
The function iterates through the string and records the first index of each lowercase letter seen. When an uppercase letter is found, it checks if the corresponding lowercase letter has been encountered before and if all its occurrences appear before this uppercase letter. A set is used to collect special letters only once.
Python
Java
JavaScript
Time Complexity: O(n), where n is the length of the word. Space Complexity: O(n) for the hashmap and set underlying the implementation.
This approach entails two passes: the first to record the last occurrence of each letter (both lower and uppercase) and the second to determine if the lowercase occurs before its uppercase counterpart.
This C solution uses an array to store the last indices for lowercase and uppercase letters separately. It first iterates to fill these indices and then checks the order to determine special characters.
Time Complexity: O(n). Space Complexity: O(1).
We define two hash tables or arrays first and last to store the positions where each letter first appears and last appears respectively.
Then we traverse the string word, updating first and last.
Finally, we traverse all lowercase and uppercase letters. If last[a] exists and first[b] exists and last[a] < first[b], it means that the letter a is a special letter, and we increment the answer by one.
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 |
|---|---|
| Using HashMaps to Track First Occurrence | Time Complexity: O(n), where n is the length of the word. Space Complexity: O(n) for the hashmap and set underlying the implementation. |
| Two-Pass Array Approach | Time Complexity: O(n). Space Complexity: O(1). |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMaps to Track First/Last Occurrence | O(n) | O(1) | General approach when using hash tables for character tracking in high-level languages |
| Two-Pass Array Approach | O(n) | O(1) | Preferred when working with fixed alphabets and aiming for faster constant factors |
3121 & 3120 Count the Number of Special Characters II & Characters I • Aryan Mittal • 2,918 views views
Watch 8 more video solutions →Practice Count the Number of Special Characters II with our built-in code editor and test cases.
Practice on FleetCode