3121

3121. Count the Number of Special Characters II (Medium)

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.

 

Example 1:

Input: word = "aaAbcBC"

Output: 3

Explanation:

The special characters are 'a', 'b', and 'c'.

Example 2:

Input: word = "abc"

Output: 0

Explanation:

There are no special characters in word.

Example 3:

Input: word = "AbBCab"

Output: 0

Explanation:

There are no special characters in word.

 

Constraints:

• 1 <= word.length <= 2 * 105
• word consists of only lowercase and uppercase English letters.

Similar Questions:

• Detect Capital (Easy)

Hints:

• For each character c, store the first occurrence of its uppercase and the last occurrence of its lowercase.

Solution 1.

// OJ: https://leetcode.com/problems/count-the-number-of-special-characters-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numberOfSpecialChars(string s) {
        int N = s.size(), ans = 0;
        vector<int> lastLower(26, N);
        for (int i = 0; i < N; ++i) {
            if (islower(s[i])) lastLower[s[i] - 'a'] = i;
        }
        for (int i = 0; i < N; ++i) {
            if (islower(s[i])) continue;
            int j = s[i] - 'A';
            ans += lastLower[j] < i;
            lastLower[j] = N;
        }
        return ans;
    }
};