Count the Number of Special Characters II

Count the Number of Special Characters II

What is this problem about?

The Count the Number of Special Characters II interview question is a more refined version of the "special character" check. A character is special if both its lowercase and uppercase versions exist in the string, but with a specific order requirement: every occurrence of the lowercase version must appear before the first occurrence of the uppercase version.

For example, in "aaAbA", 'a' is NOT special because the second 'a' is before the first 'A', but then there is another 'A' later. Wait, the rule is usually: all lowercase 'a's must be before the first uppercase 'A'. If "aaA" is the string, 'a' is special. If "aAa", 'a' is not.

Why is this asked in interviews?

Microsoft and Google use this "Medium" problem to test a candidate's ability to track multiple indices and validate chronological constraints. It evaluations hash table interview pattern skills, specifically using maps to store the "last seen" index of lowercase letters and the "first seen" index of uppercase letters. It’s a test of precise state management.

Algorithmic pattern used

This problem uses Index Tracking with Hash Tables.

1. Use a Hash Table last_lower to store the last index of each lowercase character.
2. Use a Hash Table first_upper to store the first index of each uppercase character.
3. Iterate through the string. Update last_lower for every lowercase char and only update first_upper if the char hasn't been seen in uppercase yet.
4. After one pass, iterate through the 26 letters. A letter is special if:
   • It exists in both last_lower and first_upper.
   • last_lower[c] < first_upper[c].

Example explanation

s = "abcAbC"

1. last_lower: {a:0, b:1, c:2}
2. first_upper: {A:3, C:5}
3. Check letters:
   • 'a': last lower (0) < first upper (3). (Special!)
   • 'b': no uppercase 'B'.
   • 'c': last lower (2) < first upper (5). (Special!) Total = 2.

Common mistakes candidates make

• Updating first_upper repeatedly: Forgetting to check if the uppercase character was already seen, which would overwrite the first occurrence with a later one.
• Incorrect logic for "all before": Not realizing that simply checking the last lowercase against the first uppercase covers the condition that all lowercase are before all uppercase (or at least the start of the uppercase sequence).
• Brute force: Running $O(N^2)$ checks for every pair of characters.

Interview preparation tip

When a problem specifies a "before/after" relationship between sets of indices, always focus on the boundary values: the last index of the "before" set and the first index of the "after" set.