Count the Number of Special Characters II - Video Solutions

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.