Count the Number of Special Characters II

Count the Number of Special Characters II - Problem

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.

Input & Output

Example 1 — Mixed Valid Cases

$ Input: word = "aaAbcBC"

› Output: 3

💡 Note: Special characters are 'a', 'b', and 'c'. Letter 'a': lowercase at positions 0,1 before uppercase at 2. Letter 'b': lowercase at 3 before uppercase at 5. Letter 'c': lowercase at 4 before uppercase at 6.

Example 2 — Invalid Order

$ Input: word = "abc"

› Output: 0

💡 Note: No uppercase letters exist, so no letter can be special (needs both cases).

Example 3 — Constraint Violation

$ Input: word = "AbBcC"

› Output: 0

💡 Note: All letters appear in uppercase before lowercase, violating the ordering constraint.

Constraints

1 ≤ word.length ≤ 1000
word consists of only lowercase and uppercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

String with mixed case letters: "aaAbcBC"

Process

Check each letter for both cases and proper ordering

Output

Count of valid special characters: 3

Key Takeaway

🎯 Key Insight: Track when lowercase appears after uppercase to identify invalid special characters

Asked in

G Google 45 a Amazon 32 M Microsoft 28

The key insight is tracking when lowercase letters appear after their first uppercase occurrence, making them invalid. The optimal approach uses a single pass to track state for each letter. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Hash Map	O(n)	O(1)	First pass records positions, second pass validates ordering
Brute Force - Check Each Letter Separately	O(26 × n) = O(n)	O(1)	For each letter, scan the string multiple times to check if it's special
Single Pass Optimal	O(n)	O(1)	One pass tracking transition points and invalid characters

Two-Pass Hash Map — Algorithm Steps

Step 1: Scan string to record last lowercase position for each letter
Step 2: Scan string to record first uppercase position for each letter
Step 3: Count letters where last_lower < first_upper

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Record last lowercase positions: {a:1, b:3, c:4}

Second Pass

Record first uppercase positions: {a:2, b:5, c:6}

Validate

Check ordering: a(1<2)✓, b(3<5)✓, c(4<6)✓

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int solution(char* word) {
    int lastLower[26];
    int firstUpper[26];
    bool hasLower[26] = {false};
    bool hasUpper[26] = {false};
    
    for (int i = 0; i < 26; i++) {
        lastLower[i] = -1;
        firstUpper[i] = -1;
    }
    
    int len = strlen(word);
    
    // First pass: record last lowercase positions
    for (int i = 0; i < len; i++) {
        char c = word[i];
        if (c >= 'a' && c <= 'z') {
            lastLower[c - 'a'] = i;
            hasLower[c - 'a'] = true;
        }
    }
    
    // Second pass: record first uppercase positions
    for (int i = 0; i < len; i++) {
        char c = word[i];
        if (c >= 'A' && c <= 'Z') {
            int idx = c - 'A';
            if (firstUpper[idx] == -1) {
                firstUpper[idx] = i;
                hasUpper[idx] = true;
            }
        }
    }
    
    // Count special characters
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (hasLower[i] && hasUpper[i] && lastLower[i] < firstUpper[i]) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char word[1001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the string of length n

✓ Linear Growth

Space Complexity

O(1)

Hash maps store at most 26 characters each

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler