3121. Count the Number of Special Characters II

題目 / Problem

給你一個字串 word。如果一個字母 c 同時以小寫和大寫出現在 word 中，而且 c 的每一個小寫出現位置都在它第一個大寫出現位置之前，那麼這個字母 c 就稱為特殊（special） 的。請回傳 word 中特殊字母的數量。

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.

Constraints / 限制： - 1 <= word.length <= 2 * 10^5 - word 只由大小寫英文字母組成 / consists of only lowercase and uppercase English letters.

Worked example / 範例： word = "aaAbcBC" → output 3. 特殊字母是 'a'、'b'、'c'，因為每個字母的所有小寫都排在它第一個大寫之前。

名詞解釋 / Glossary

• 計數陣列 / counting array：一個固定大小的陣列（這裡用大小 26，對應 26 個英文字母），用整數索引直接記錄某個資訊。比用雜湊表更快、更省記憶體，因為字母種類有限。
• 索引 / index：字元在字串中的位置（從 0 開始算）。word[0] 是第一個字元。
• 大小寫判斷 / case check：用 c >= 'a' && c <= 'z' 判斷是否小寫；'a'、'A' 等字元在 C/C++ 中其實是整數（ASCII 碼），可以直接比較大小。
• 字母對應到 0–25 / mapping a letter to 0–25：用 c - 'a'（小寫）或 c - 'A'（大寫）把字母轉成 0 到 25 的索引，當作陣列下標使用。
• 哨兵值 / sentinel value：一個「不可能是真實答案」的特殊初始值（這裡用 -1），用來表示「還沒看到過」。

思路

最直接的暴力法是：對每個字母（a–z 共 26 種），掃過整個字串，找出它所有小寫的位置和所有大寫的位置，再檢查條件。但這樣每個字母都掃一次字串，總共要掃 26 次，雖然也能過，但其實沒必要。我們真正需要知道的，並不是「所有」位置，而是兩個關鍵點：這個字母最後一次出現小寫的位置，以及它第一次出現大寫的位置。為什麼是這兩個？因為「每個小寫都在第一個大寫之前」這個條件，等價於「最晚的那個小寫，也在最早的那個大寫之前」。只要最後一個小寫的索引小於第一個大寫的索引，所有小寫自然都在前面。於是我們開兩個大小為 26 的計數陣列：lastLower 記錄每個字母最後一次小寫的索引，firstUpper 記錄每個字母第一次大寫的索引，都初始化為 -1 表示尚未出現。只掃一遍字串就能把它們全部填好——遇到小寫就更新（覆蓋）lastLower，遇到大寫就只在第一次寫入 firstUpper。最後對 26 個字母逐一檢查：兩者都出現過（不是 -1），且 lastLower < firstUpper，就算一個特殊字母。整個過程只掃字串一次，是線性時間。

The brute-force idea is: for each of the 26 letters, scan the whole string to collect every lowercase position and every uppercase position, then check the rule. That re-scans the string 26 times, which is wasteful. The insight is that we don't need all positions — only two: the last index where the letter appears lowercase, and the first index where it appears uppercase. The condition "every lowercase comes before the first uppercase" is exactly equivalent to "the latest lowercase comes before the earliest uppercase." If the last lowercase index is smaller than the first uppercase index, then every lowercase is necessarily before it. So we keep two size-26 counting arrays: lastLower[c] and firstUpper[c], both initialized to -1 (meaning "not seen"). A single pass fills them — on a lowercase letter we overwrite lastLower (so it ends up holding the last one), and on an uppercase letter we set firstUpper only the first time. Finally we check all 26 letters: a letter is special when both values exist (not -1) and lastLower < firstUpper. One pass over the string makes this linear time.

逐步走查 / Walkthrough

Input word = "aaAbcBC". Index/字元對照：0:'a' 1:'a' 2:'A' 3:'b' 4:'c' 5:'B' 6:'C'. 初始 lastLower 和 firstUpper 全為 -1。

最後逐字母檢查 / final per-letter check： - a: lastLower=1, firstUpper=2 → 都存在且 1 < 2 ✅ special - b: lastLower=3, firstUpper=5 → 3 < 5 ✅ special - c: lastLower=4, firstUpper=6 → 4 < 6 ✅ special - 其餘字母兩者皆為 -1，跳過 / all other letters stay -1, skipped.

計數 / count = 3. ✅

Solution — C

// 演算法 / Algorithm:
// 掃一遍字串，記錄每個字母「最後一次小寫」和「第一次大寫」的索引。
// One pass: record each letter's last-lowercase index and first-uppercase index.
// 若兩者都存在且 lastLower < firstUpper，該字母即為 special。
// A letter is special if both exist and lastLower < firstUpper.

int numberOfSpecialChars(char* word) {
    // lastLower[k] = 字母 k 最後一次以小寫出現的索引；-1 表示尚未出現
    // lastLower[k] = index of the last lowercase occurrence of letter k; -1 = not seen
    int lastLower[26];
    // firstUpper[k] = 字母 k 第一次以大寫出現的索引；-1 表示尚未出現
    // firstUpper[k] = index of the first uppercase occurrence of letter k; -1 = not seen
    int firstUpper[26];

    // 初始化兩個陣列為 -1（哨兵值，代表「還沒看到」）
    // Initialize both arrays to -1 (sentinel meaning "not yet seen")
    for (int k = 0; k < 26; k++) {
        lastLower[k] = -1;   // 尚無小寫 / no lowercase yet
        firstUpper[k] = -1;  // 尚無大寫 / no uppercase yet
    }

    // 逐字元掃描；word[i] != '' 是 C 字串結尾（空字元）的判斷
    // Scan char by char; '' (null terminator) marks the end of a C string
    for (int i = 0; word[i] != ''; i++) {
        char c = word[i];  // 取出目前字元 / current character
        if (c >= 'a' && c <= 'z') {
            // 小寫：c - 'a' 把字母映射到 0..25 當作索引；每次覆蓋以保留「最後一次」
            // Lowercase: c - 'a' maps the letter to 0..25; overwrite to keep the LAST index
            lastLower[c - 'a'] = i;
        } else {
            // 大寫：只在第一次（仍為 -1）寫入，以保留「第一次」出現的位置
            // Uppercase: only write when still -1, so it keeps the FIRST occurrence
            if (firstUpper[c - 'A'] == -1) {
                firstUpper[c - 'A'] = i;
            }
        }
    }

    int count = 0;  // 特殊字母計數 / number of special letters
    for (int k = 0; k < 26; k++) {
        // 條件：小寫和大寫都出現過，且最後一個小寫在第一個大寫之前
        // Condition: both cases appeared, and last lowercase is before first uppercase
        if (lastLower[k] != -1 && firstUpper[k] != -1 && lastLower[k] < firstUpper[k]) {
            count++;  // 符合，計入 / matches, count it
        }
    }
    return count;  // 回傳答案 / return the result
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：一次掃描記錄每個字母的「最後小寫索引」與「第一大寫索引」，
// Same as the C version: one pass records each letter's last-lowercase and
// first-uppercase index, then count letters where lastLower < firstUpper.

class Solution {
public:
    int numberOfSpecialChars(string word) {
        // vector<int> 是會自動管理記憶體的動態陣列；這裡固定 26 格，初值 -1
        // vector<int> is a dynamic array that manages its own memory; size 26, init -1
        vector<int> lastLower(26, -1);   // 每字母最後一次小寫的索引 / last lowercase index
        vector<int> firstUpper(26, -1);  // 每字母第一次大寫的索引 / first uppercase index

        // range-for：依序取出 word 中每個字元；i 同步追蹤索引
        // range-for iterates each char of word; i tracks the index in parallel
        for (int i = 0; i < (int)word.size(); i++) {
            char c = word[i];  // 目前字元 / current character
            if (islower(c)) {
                // islower：標準函式，判斷是否小寫；c - 'a' 映射成 0..25 的索引
                // islower: standard function testing lowercase; c - 'a' maps to 0..25
                lastLower[c - 'a'] = i;        // 覆蓋以保留最後一次 / keep the last one
            } else {
                // 只在尚未記錄（-1）時寫入，保留第一次大寫位置
                // Write only if not recorded yet (-1) to keep the first uppercase
                if (firstUpper[c - 'A'] == -1)
                    firstUpper[c - 'A'] = i;
            }
        }

        int count = 0;  // 特殊字母數量 / count of special letters
        for (int k = 0; k < 26; k++) {
            // 兩者皆出現且最後小寫早於第一大寫 → special
            // both exist AND last lowercase precedes first uppercase → special
            if (lastLower[k] != -1 && firstUpper[k] != -1 && lastLower[k] < firstUpper[k])
                count++;
        }
        return count;  // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。我們只掃字串一次填表（O(n)），最後檢查固定的 26 個字母（O(26)，視為常數）。主導項是那一次掃描，所以是線性。 / We scan the string once to fill the arrays, then do a constant 26-letter check; the single pass dominates, giving linear time.
• Space: O(1) — 只用了兩個固定大小 26 的陣列，不隨輸入長度增長，因此是常數空間。 / Only two fixed size-26 arrays, independent of input length, so constant space.

Pitfalls & Edge Cases

• 小寫要取「最後」、大寫要取「第一」/ last for lowercase, first for uppercase：若不小心對大寫也用覆蓋（變成最後一個大寫），條件就錯了。第一個大寫才是真正的分界線。 / Overwriting uppercase would store the last uppercase instead of the first; the first uppercase is the real boundary, so guard it with the == -1 check.
• 別忘了「兩者都要出現」/ both cases must appear：只有小寫或只有大寫的字母（其中一個仍是 -1）不算 special，所以必須同時檢查 lastLower != -1 與 firstUpper != -1。 / A letter with only one case (the other still -1) is not special; check both are non-negative.
• 哨兵值的選擇 / sentinel choice：用 -1 是因為合法索引都是 0 以上，-1 不可能與真實位置混淆。 / -1 works because valid indices are ≥ 0, so it can never collide with a real position.
• 嚴格小於，不是小於等於 / strict <, not <=：同一個字母不可能在同一索引同時是大寫和小寫，所以 < 與 <= 在此題其實等價，但用 < 語意最清楚（小寫嚴格在大寫之前）。 / A single index can't be both cases, but < best expresses "strictly before."
• 大字串效能 / large input：n 可達 2×10⁵，O(26·n) 的暴力法雖能過，但本解的單次掃描更穩、更省。 / The 26-pass brute force would also pass, but the single-pass solution is cleaner and faster.