Skip to main content
Talentd

Count the Number of Special Characters II - Solution & Explanation

MediumHash TableString11 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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 * 105
  • word consists of only lowercase and uppercase English letters.

Approach Overview

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.

Approach 1: Using HashMaps to Track First Occurrence

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the word. Space Complexity: O(n) for the hashmap and set underlying the implementation.

Try this approach in the editor →

Approach 2: Two-Pass Array Approach

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.

Code

CC++C#

C

C++

C#

Complexity

Time Complexity: O(n). Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Hash Table or Array

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMaps to Track First/Last OccurrenceO(n)O(1)General approach when using hash tables for character tracking in high-level languages
Two-Pass Array ApproachO(n)O(1)Preferred when working with fixed alphabets and aiming for faster constant factors

Video Solution

Count the Number of Special Characters II | Simplest Explanation | Dry Run | Leetcode 3121 | MIK • codestorywithMIK • 4,822 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count the Number of Special Characters II easy or hard?
The problem is classified as Medium difficulty. The main challenge is recognizing the ordering constraint between lowercase and uppercase occurrences and storing positions efficiently so the validation step can be done in constant time per character.
Count the Number of Special Characters II Python/Java solution
Python and Java implementations commonly use dictionaries or arrays to record the first uppercase and last lowercase positions. After scanning the string once, a loop over the alphabet counts valid characters. Both implementations achieve O(n) time and O(1) space complexity.
How to solve Count the Number of Special Characters II in O(n)?
Scan the string and store two values for each letter: the last index of its lowercase form and the first index of its uppercase form. After the scan, iterate over all 26 characters and count those where both exist and the lowercase index is smaller than the uppercase index. This ensures all lowercase occurrences appear before the first uppercase occurrence.
What is the best approach for Count the Number of Special Characters II?
The best approach runs in O(n) time by recording the last index of each lowercase letter and the first index of each uppercase letter. After scanning the string once, check whether the last lowercase index occurs before the first uppercase index for each character. This guarantees the required ordering while keeping space usage constant.
Is Count the Number of Special Characters II asked at Google/Amazon/Meta?
Problems involving character tracking, case comparisons, and hash table lookups frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests string traversal, indexing logic, and efficient use of constant-sized data structures, which are common interview patterns.
What data structure is used in Count the Number of Special Characters II?
The solution typically uses a hash table or fixed-size arrays to store character positions. Hash maps provide flexible key lookups, while arrays of size 26 offer faster indexing because the alphabet size is constant.
What is the time complexity of Count the Number of Special Characters II?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once to record its position, and then a constant loop over 26 letters verifies the conditions. Space complexity remains O(1) because only fixed-size arrays or maps for the alphabet are used.

Ready to solve this problem?

Practice Count the Number of Special Characters II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Special Characters I

Next

Detect Capital