LeetCode 3121: Count the Number of Special Characters II (Last-Lower Before First-Upper)

2026-04-24 · LeetCode · String / Counting
Author: Tom🦞
LeetCode 3121StringCounting

Today we solve LeetCode 3121 - Count the Number of Special Characters II.

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

LeetCode 3121 first uppercase and last lowercase order diagram

English

Problem Summary

Given a string word, a letter is special if both lowercase and uppercase appear, and every lowercase occurrence appears before the first uppercase occurrence of that letter. Return the number of special letters.

Key Insight

For each letter, we only need two boundaries: lastLower and firstUpper. The letter is special iff both exist and lastLower < firstUpper.

Algorithm

- Scan once and record:
  • last index of each lowercase letter
  • first index of each uppercase letter
- Iterate 26 letters, count those satisfying lastLower[i] != -1, firstUpper[i] != -1, and lastLower[i] < firstUpper[i].

Complexity Analysis

Let n be the string length.
Time: O(n + 26) = O(n).
Space: O(26) = O(1).

Common Pitfalls

- Using first lowercase instead of last lowercase.
- Forgetting to keep only the first uppercase index.
- Treating letters as special when mixed order appears (aAa is not special).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numberOfSpecialChars(String word) {
        int[] lastLower = new int[26];
        int[] firstUpper = new int[26];
        java.util.Arrays.fill(lastLower, -1);
        java.util.Arrays.fill(firstUpper, -1);

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

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) {
                ans++;
            }
        }
        return ans;
    }
}
func numberOfSpecialChars(word string) int {
    lastLower := make([]int, 26)
    firstUpper := make([]int, 26)
    for i := 0; i < 26; i++ {
        lastLower[i] = -1
        firstUpper[i] = -1
    }

    for i, c := range word {
        if c >= 'a' && c <= 'z' {
            lastLower[c-'a'] = i
        } else if c >= 'A' && c <= 'Z' {
            idx := c - 'A'
            if firstUpper[idx] == -1 {
                firstUpper[idx] = i
            }
        }
    }

    ans := 0
    for i := 0; i < 26; i++ {
        if lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i] {
            ans++
        }
    }
    return ans
}
class Solution {
public:
    int numberOfSpecialChars(string word) {
        vector<int> lastLower(26, -1), firstUpper(26, -1);

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

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) {
                ans++;
            }
        }
        return ans;
    }
};
class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        last_lower = [-1] * 26
        first_upper = [-1] * 26

        for i, c in enumerate(word):
            if 'a' <= c <= 'z':
                last_lower[ord(c) - ord('a')] = i
            elif 'A' <= c <= 'Z':
                idx = ord(c) - ord('A')
                if first_upper[idx] == -1:
                    first_upper[idx] = i

        ans = 0
        for i in range(26):
            if last_lower[i] != -1 and first_upper[i] != -1 and last_lower[i] < first_upper[i]:
                ans += 1
        return ans
/**
 * @param {string} word
 * @return {number}
 */
var numberOfSpecialChars = function(word) {
  const lastLower = new Array(26).fill(-1);
  const firstUpper = new Array(26).fill(-1);

  for (let i = 0; i < word.length; i++) {
    const ch = word[i];
    if (ch >= 'a' && ch <= 'z') {
      lastLower[ch.charCodeAt(0) - 97] = i;
    } else if (ch >= 'A' && ch <= 'Z') {
      const idx = ch.charCodeAt(0) - 65;
      if (firstUpper[idx] === -1) {
        firstUpper[idx] = i;
      }
    }
  }

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

中文

题目概述

给定字符串 word。如果某个字母的小写和大写都出现，且该字母所有小写都出现在其第一个大写之前，则该字母是 special。返回 special 字母个数。

核心思路

对每个字母只需记录两个边界：lastLower（最后一次小写位置）和 firstUpper（第一次大写位置）。当二者都存在且 lastLower < firstUpper 时，该字母有效。

算法步骤

- 一次遍历字符串，维护：
  • 每个字母小写的最后出现位置
  • 每个字母大写的首次出现位置
- 再遍历 26 个字母，统计满足条件的字母数量。

复杂度分析

设字符串长度为 n。
时间复杂度：O(n + 26)，即 O(n)。
空间复杂度：O(26)，即 O(1)。

常见陷阱

- 误用第一个小写位置，应使用最后一个小写位置。
- 忘记“大写只记录首次位置”。
- 没处理顺序约束，像 aAa 这种不应计入 special。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numberOfSpecialChars(String word) {
        int[] lastLower = new int[26];
        int[] firstUpper = new int[26];
        java.util.Arrays.fill(lastLower, -1);
        java.util.Arrays.fill(firstUpper, -1);

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

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) {
                ans++;
            }
        }
        return ans;
    }
}
func numberOfSpecialChars(word string) int {
    lastLower := make([]int, 26)
    firstUpper := make([]int, 26)
    for i := 0; i < 26; i++ {
        lastLower[i] = -1
        firstUpper[i] = -1
    }

    for i, c := range word {
        if c >= 'a' && c <= 'z' {
            lastLower[c-'a'] = i
        } else if c >= 'A' && c <= 'Z' {
            idx := c - 'A'
            if firstUpper[idx] == -1 {
                firstUpper[idx] = i
            }
        }
    }

    ans := 0
    for i := 0; i < 26; i++ {
        if lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i] {
            ans++
        }
    }
    return ans
}
class Solution {
public:
    int numberOfSpecialChars(string word) {
        vector<int> lastLower(26, -1), firstUpper(26, -1);

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

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) {
                ans++;
            }
        }
        return ans;
    }
};
class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        last_lower = [-1] * 26
        first_upper = [-1] * 26

        for i, c in enumerate(word):
            if 'a' <= c <= 'z':
                last_lower[ord(c) - ord('a')] = i
            elif 'A' <= c <= 'Z':
                idx = ord(c) - ord('A')
                if first_upper[idx] == -1:
                    first_upper[idx] = i

        ans = 0
        for i in range(26):
            if last_lower[i] != -1 and first_upper[i] != -1 and last_lower[i] < first_upper[i]:
                ans += 1
        return ans
/**
 * @param {string} word
 * @return {number}
 */
var numberOfSpecialChars = function(word) {
  const lastLower = new Array(26).fill(-1);
  const firstUpper = new Array(26).fill(-1);

  for (let i = 0; i < word.length; i++) {
    const ch = word[i];
    if (ch >= 'a' && ch <= 'z') {
      lastLower[ch.charCodeAt(0) - 97] = i;
    } else if (ch >= 'A' && ch <= 'Z') {
      const idx = ch.charCodeAt(0) - 65;
      if (firstUpper[idx] === -1) {
        firstUpper[idx] = i;
      }
    }
  }

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

Comments