LogoKode$word

LeetCode 3121: Count the Number of Special Characters II – Java HashMap Solution Explained

Learn how to solve LeetCode 3121 Count the Number of Special Characters II using HashMap in Java. Includes intuition, brute force approach, optimized solution, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
3 views
LinkedInGithubX
0
0
LeetCodeJavaHashMapStringMedium
LeetCode 3121: Count the Number of Special Characters II – Java HashMap Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 3121 – Count the Number of Special Characters II is an interesting string and hashing problem that extends the logic of the previous Special Characters problem.

This problem tests:

  1. Character indexing
  2. String traversal
  3. HashMap usage
  4. Uppercase and lowercase handling
  5. Order-based conditions

Unlike Part I, this version adds an important restriction:

Every lowercase occurrence must appear before the first uppercase occurrence.

This additional condition makes the problem more challenging and interview-relevant.

Problem Link

🔗 https://leetcode.com/problems/count-the-number-of-special-characters-ii/

Problem Statement

You are given a string:

word

A character is called:

special

if:

  1. It appears in both lowercase and uppercase
  2. Every lowercase occurrence appears before the first uppercase occurrence

Return:

Number of special characters

Example 1

Input

word = "aaAbcBC"

Output

3

Explanation

Special characters:

'a'
'b'
'c'

because:

  1. Lowercase letters appear first
  2. Uppercase letters appear later

Example 2

Input

word = "abc"

Output:

0

No uppercase letters exist.

Example 3

Input

word = "AbBCab"

Output:

0

Explanation:

Lowercase letters appear after uppercase letters.

Condition fails.

Key Observation

For a character to be special:

Last lowercase index < First uppercase index

This is the entire logic of the problem.

Intuition

We need two pieces of information.

For every character:

  1. Last occurrence of lowercase letter
  2. First occurrence of uppercase letter

If:

lastLowercase < firstUppercase

then character is special.

Brute Force Approach

Idea

For every character:

  1. Traverse entire string
  2. Find lowercase occurrences
  3. Find uppercase occurrences
  4. Verify ordering condition

Brute Force Complexity

Time Complexity

O(N²)

because repeated traversal is required.

Space Complexity

O(1)

Optimized HashMap Approach

Idea

Use two HashMaps:

  1. Lowercase map stores last index
  2. Uppercase map stores first index

Then compare indices.

Java Solution

class Solution {

public int numberOfSpecialChars(String word) {

HashMap<Character, Integer> lower = new HashMap<>();
HashMap<Character, Integer> upper = new HashMap<>();

for(int i = 0; i < word.length(); i++) {

if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') {
lower.put(word.charAt(i), i);
}
else {

if(!upper.containsKey(word.charAt(i))) {
upper.put(word.charAt(i), i);
}
}
}

int ans = 0;

for(int i = 0; i < word.length(); i++) {

char up = Character.toUpperCase(word.charAt(i));

if(lower.containsKey(word.charAt(i)) && upper.containsKey(up)) {

if(lower.get(word.charAt(i)) < upper.get(up)) {

ans++;

lower.remove(word.charAt(i));
upper.remove(up);
}
}
}

return ans;
}
}

Cleaner Optimized Version

class Solution {

public int numberOfSpecialChars(String word) {

int[] lastLower = new int[26];
int[] firstUpper = new int[26];

Arrays.fill(lastLower, -1);
Arrays.fill(firstUpper, Integer.MAX_VALUE);

for(int i = 0; i < word.length(); i++) {

char ch = word.charAt(i);

if(Character.isLowerCase(ch)) {
lastLower[ch - 'a'] = i;
}
else {
firstUpper[ch - 'A'] = Math.min(firstUpper[ch - 'A'], i);
}
}

int count = 0;

for(int i = 0; i < 26; i++) {

if(lastLower[i] != -1 &&
firstUpper[i] != Integer.MAX_VALUE &&
lastLower[i] < firstUpper[i]) {

count++;
}
}

return count;
}
}

Why This Works

For every character:

We store:

last lowercase position

and:

first uppercase position

Then simply check:

lastLowercase < firstUppercase

If true:

Character satisfies problem condition.

Dry Run

Input

word = "aaAbcBC"

Step 1: Store Indices

Lowercase positions:

'a' → 1
'b' → 3
'c' → 4

Uppercase positions:

'A' → 2
'B' → 5
'C' → 6

Step 2: Compare

1 < 2 → valid
3 < 5 → valid
4 < 6 → valid

Count becomes:

3

Final Answer

3

Time Complexity Analysis

Optimized HashMap Solution

Time Complexity

O(N)

because string traversal happens once.

Space Complexity

O(1)

Maximum alphabet size remains fixed.

Brute Force vs Optimized

ApproachTime ComplexitySpace Complexity
Brute ForceO(N²)O(1)
HashMap / Array ApproachO(N)O(1)

Interview Explanation

In interviews, explain:

A character is special only if its last lowercase occurrence appears before its first uppercase occurrence. We track indices efficiently using HashMaps or arrays.

This demonstrates:

  1. String manipulation skills
  2. Index tracking
  3. Hashing knowledge
  4. Optimization thinking

Common Mistakes

1. Checking Only Presence

Many solutions only verify:

lowercase exists && uppercase exists

But ordering condition is also required.

2. Storing Wrong Indices

We need:

  1. Last lowercase index
  2. First uppercase index

not the opposite.

3. Double Counting Characters

Always remove counted characters or use controlled traversal.

4. Ignoring Case Conversion

Always convert correctly using:

Character.toUpperCase(ch)

FAQs

Q1. Why store last lowercase occurrence?

Because all lowercase letters must appear before uppercase.

Q2. Why store first uppercase occurrence?

Because it defines the earliest uppercase appearance.

Q3. Can arrays replace HashMaps?

Yes.

Arrays are even more optimized because alphabet size is fixed.

Q4. Is this problem interview important?

Yes.

It tests:

  1. String traversal
  2. Index tracking
  3. Character handling
  4. Optimization techniques

Related Problems

Practice these next:

  1. Count the Number of Special Characters I
  2. First Unique Character in a String
  3. Valid Anagram

Conclusion

LeetCode 3121 is an excellent medium-level hashing and string problem.

It teaches:

  1. Efficient index tracking
  2. HashMap usage
  3. Order-based validation
  4. Character manipulation

The key insight is:

A character is special only if its last lowercase occurrence appears before its first uppercase occurrence.

Once this pattern becomes clear, many advanced string indexing problems become much easier.

Related Articles

LeetCode 3120: Count the Number of Special Characters I – Java HashSet Solution Explained

LeetCode 3120: Count the Number of Special Characters I – Java HashSet Solution Explained

Learn how to solve LeetCode 3120 Count the Number of Special Characters I using HashSet in Java. Includes intuition, brute force approach, optimized solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Learn How to Solve the Word Pattern Problem Using HashMaps, Bidirectional Mapping, and Index Mapping Techniques

Read Article
LeetCode 844: Backspace String Compare — Java Solution With All Approaches Explained

LeetCode 844: Backspace String Compare — Java Solution With All Approaches Explained

Learn How to Compare Two Strings After Backspace Operations Using StringBuilder, Stack, and O(1) Space Two Pointer — With Step-by-Step Dry Run and Full Complexity Analysis in Java

Read Article
Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Mastering the Sliding Window Pattern with Frequency Optimization

Read Article
Ai Assistant Kas