Strings

Ordering Matters: Solving Count the Number of Special Characters II

May 2026
10 min read

At first glance, this problem looks like a simple uppercase/lowercase matching question. But the real challenge lies in understanding that ordering matters more than existence.

Introduction

Some interview problems become difficult not because of implementation complexity, but because of interpretation complexity.

Count the Number of Special Characters II is one of those problems.

At first glance, it looks extremely similar to:

  • lowercase/uppercase matching
  • set-based lookup
  • simple character existence checking

But the real trick is hidden inside a single word:

BEFORE

That tiny condition completely changes the problem.

Understanding the Problem

We are given a string containing:

  • lowercase letters
  • uppercase letters

A character becomes “special” only if:

  1. Both lowercase and uppercase versions exist
  2. ALL lowercase occurrences appear BEFORE the FIRST uppercase occurrence

Important Clarification

This condition is extremely strict.

Example:

text
aA ✅

Valid because:

  • lowercase 'a' appears before uppercase 'A'

But:

text
Aa ❌

Invalid because:

  • uppercase appears first

Even more importantly:

text
aaAA ✅

Still valid.

Because every lowercase 'a' appears before first uppercase 'A'.

But:

text
aAa ❌

Invalid.

Because:

  • lowercase 'a' appears AFTER uppercase 'A'

That single violation destroys the pair.

Why This Problem Is Deceptive

Many developers initially think:

“If lowercase and uppercase both exist, count it.”

That logic solves:

text
Count the Number of Special Characters I

But NOT this problem.

This version is fundamentally about:

  • ordering
  • positions
  • timeline validation

Existence alone is insufficient.

Understanding Through Example

Consider:

text
word = "cDCbc"

Indexes:

text
0 -> c
1 -> D
2 -> C
3 -> b
4 -> c

Now evaluate:

text
c / C

We have:

  • lowercase c exists
  • uppercase C exists

Initially this looks valid.

But observe positions carefully:

text
First uppercase C = index 2
Last lowercase c = index 4

Condition required:

text
last lowercase < first uppercase

But:

text
4 < 2 ❌

Therefore:

Character is NOT special.

Final answer becomes:

text
0

The Core Insight

For every character:

We only care about:

  • LAST lowercase occurrence
  • FIRST uppercase occurrence

Why?

Because:

If even one lowercase letter appears after uppercase, the pair becomes invalid.

So:

text
last lowercase index < first uppercase index

is the entire condition.

That observation simplifies the problem dramatically.

Why HashSet Fails

A very common beginner mistake is using:

java
Set<Character>

A set only tells:

text
exists / does not exist

But this problem depends on:

text
where characters occurred

Sets completely lose positional information.

That is why index tracking becomes mandatory.

The Elegant Array Optimization

Instead of using maps:

we use two arrays:

java
int[] lower = new int[26];
int[] upper = new int[26];

Each index represents a character.

Example:

text
0 -> a
1 -> b
2 -> c
...
25 -> z

What Each Array Stores

lower[]

Stores:

text
LAST lowercase occurrence

Example:

java
lower[ch - 'a'] = i;

upper[]

Stores:

text
FIRST uppercase occurrence

Example:

java
if (upper[ch - 'A'] == -1) {
    upper[ch - 'A'] = i;
}

We only store first uppercase occurrence.

Later uppercase appearances do not matter.

Visual Dry Run

Input:

text
"aabBcC"

Indexes:

text
0 -> a
1 -> a
2 -> b
3 -> B
4 -> c
5 -> C

Building Arrays

lower[]

text
a -> 1
b -> 2
c -> 4

upper[]

text
B -> 3
C -> 5

Validation

For b:

text
2 < 3 ✅

Valid.

For c:

text
4 < 5 ✅

Valid.

Final answer:

text
2

Why This Works

The algorithm works because:

  • last lowercase captures worst-case lowercase position
  • first uppercase captures earliest uppercase position

If ordering survives this comparison:

the character pair is guaranteed valid.

Complexity Analysis

Time Complexity

O(N)

Single traversal through string.

Space Complexity

O(1)

Arrays always remain fixed size:

text
26

regardless of input size.

Common Mistakes

Using HashSet

Cannot track ordering.

Returning 0 Immediately

Only one character pair may fail.

Entire answer should not instantly become invalid.

Tracking First Lowercase Instead of Last

We must verify ALL lowercase letters appear before uppercase.

Therefore:

LAST lowercase matters.

Tracking Last Uppercase

Only FIRST uppercase matters.

Because violation begins there.

Pattern Recognition

This problem teaches an important interview lesson:

Some problems are about existence. Others are about ordering.

Ordering-based problems almost always require:

  • index tracking
  • timeline reasoning
  • prefix/suffix thinking
  • positional validation

Recognizing that shift is the real challenge.

Final Thoughts

The brilliance of this problem lies in how a tiny wording detail completely changes the solution strategy.

Without careful reading, it looks like a simple set problem.

But once ordering enters the picture, the entire problem transforms into an index-tracking challenge.

That transition from existence checking to timeline validation is exactly what makes this problem deceptively powerful.

Implementation

java
class Solution { public int numberOfSpecialChars(String word) { int[] lower = new int[26]; int[] upper = new int[26]; Arrays.fill(lower, -1); Arrays.fill(upper, -1); for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if (Character.isLowerCase(ch)) { // Store LAST lowercase occurrence lower[ch - 'a'] = i; } else { // Store FIRST uppercase occurrence if (upper[ch - 'A'] == -1) { upper[ch - 'A'] = i; } } } int count = 0; for (int i = 0; i < 26; i++) { if (lower[i] != -1 && upper[i] != -1 && lower[i] < upper[i]) { count++; } } return count; } }