Count the Number of Special Characters II — Editorial

Opening the reading…

Intuitionturning every occurrence condition into two boundary positions

For one letter, every lowercase occurrence must come before the first uppercase occurrence. The only lowercase occurrence that can violate this rule is the last one: if even the last lowercase is before the first uppercase, then all earlier lowercase occurrences are also before it. Therefore, each letter needs only two positions: its last lowercase occurrence and its first uppercase occurrence.

Scan the string once and record those two boundaries for each of the 26 letters. A letter is special exactly when both boundaries exist and the last lowercase position is smaller than the first uppercase position. This also handles repeated letters without comparing every pair of occurrences.

Approachone scan, then one check per letter

Create firstUpper and lastLower arrays filled with -1, because -1 distinguishes a letter that never appears in the corresponding case from a position at the start of the string.

Scan word from left to right and update lastLower for every lowercase character, because the latest lowercase position is the only lowercase boundary that matters.

For an uppercase character, store its position only if it is the first uppercase occurrence, because later uppercase occurrences cannot make the required ordering easier to satisfy.

Loop over all 26 letters and require both stored positions to exist, because a letter appearing in only one case is not special.

Count the letter when lastLower is smaller than firstUpper, because that inequality says every lowercase occurrence lies before the first uppercase occurrence.

Return the count after the fixed 26-letter check, because no character outside the English alphabet can contribute.

Complexitythe input length controls the scan; the alphabet is fixed

MEASURE	BOUND	WHY
Time	O(n)	The string is scanned once, and each character updates one array entry in constant time. The later loop examines exactly 26 letters, so its cost is constant and does not grow with n.
Space	O(1) extra	The two arrays contain 26 positions each, regardless of n. The returned integer is output rather than working memory, and no storage grows with the input.

Here n is the length of word; the alphabet has exactly 26 letters, so its storage and final scan are constant-sized.

Annotated solutionC++ · boundary arrays · the direct position-based solution

CPPStore the last lowercase and first uppercase position for every letter, then count valid pairs of boundaries.

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    int numberOfSpecialChars(string word) {
        int firstUpper[26];
        int lastLower[26];
        fill(firstUpper, firstUpper + 26, -1);
        fill(lastLower, lastLower + 26, -1);

        for (int i = 0; i < static_cast<int>(word.size()); ++i) {
            char c = word[i];
            if (c >= 'a' && c <= 'z') {
                lastLower[c - 'a'] = i;
            } else {
                int index = c - 'A';
                if (firstUpper[index] == -1) {
                    firstUpper[index] = i;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < 26; ++i) {
            if (lastLower[i] != -1 &&
                firstUpper[i] != -1 &&
                lastLower[i] < firstUpper[i]) {
                ++answer;
            }
        }
        return answer;
    }
};

The placement of the two updates is the key detail. Lowercase positions are overwritten, so lastLower always ends at the final lowercase occurrence. Uppercase positions are written only once, so firstUpper remains the earliest uppercase occurrence. Comparing these two extreme positions is sufficient: if the latest lowercase is early enough, every other lowercase is early enough too.

The one-pass state alternativesame bounds, but the ordering rule is recorded as a violation

You can also decide the ordering while scanning. Mark that a letter has appeared in uppercase, mark that it has appeared in lowercase, and mark the letter invalid whenever a lowercase occurrence arrives after an uppercase one. At the end, count letters that appeared in both cases and were never marked invalid. This is a different arrangement rather than an optimisation: it still uses O(n) time and O(1) extra space, while the boundary version states the proof more directly.

CPPRecord whether a lowercase occurrence appears after an uppercase occurrence, then count letters with no such violation.

#include <string>
using namespace std;

class Solution {
public:
    int numberOfSpecialChars(string word) {
        bool seenUpper[26] = {};
        bool seenLower[26] = {};
        bool invalid[26] = {};

        for (char c : word) {
            if (c >= 'a' && c <= 'z') {
                int index = c - 'a';
                seenLower[index] = true;
                if (seenUpper[index]) {
                    invalid[index] = true;
                }
            } else {
                seenUpper[c - 'A'] = true;
            }
        }

        int answer = 0;
        for (int i = 0; i < 26; ++i) {
            if (seenLower[i] && seenUpper[i] && !invalid[i]) {
                ++answer;
            }
        }
        return answer;
    }
};