3121. Count the Number of Special Characters II

Hash Table
String

TIME

O(n)

SPACE

O(1)

Intuition

For each letter, we need two facts:

whether it appears in uppercase, and where the first uppercase occurrence is
where its last lowercase occurrence is

A letter is special only if both cases appear and the last lowercase occurrence comes before the first uppercase occurrence.

Approach

Create an array lastLowercase of size 26, initialized to -1.
Create an array firstUppercase of size 26, initialized to n.
Scan word from left to right:
- for a lowercase character, update its last lowercase index
- for an uppercase character, keep the minimum uppercase index
For each of the 26 letters, count it when:
- lastLowercase[letter] != -1
- firstUppercase[letter] != n
- lastLowercase[letter] < firstUppercase[letter]

Complexity

Time: O(n), scan the string once, then check 26 letters
Space: O(1), two fixed-size arrays

Edge Cases

Only lowercase letters -> answer is 0
Only uppercase letters -> answer is 0
Uppercase before lowercase -> not special
Lowercase both before and after uppercase -> not special because not every lowercase appears before the first uppercase

Code

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        """
        3121. Count the Number of Special Characters II
        Time: O(n)
        Space: O(1)
        """
        n = len(word)
        last_lowercase = [-1] * 26
        first_uppercase = [n] * 26

        for index, char in enumerate(word):
            if char.islower():
                letter = ord(char) - ord("a")
                last_lowercase[letter] = index
            else:
                letter = ord(char) - ord("A")
                first_uppercase[letter] = min(first_uppercase[letter], index)

        answer = 0
        for letter in range(26):
            if (
                last_lowercase[letter] != -1
                and first_uppercase[letter] != n
                and last_lowercase[letter] < first_uppercase[letter]
            ):
                answer += 1

        return answer

/**
 * 3121. Count the Number of Special Characters II
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int numberOfSpecialChars(String word) {
        int n = word.length();
        int[] lastLowercase = new int[26];
        int[] firstUppercase = new int[26];

        for (int letter = 0; letter < 26; letter++) {
            lastLowercase[letter] = -1;
            firstUppercase[letter] = n;
        }

        for (int index = 0; index < n; index++) {
            char current = word.charAt(index);
            if (Character.isLowerCase(current)) {
                int letter = current - 'a';
                lastLowercase[letter] = index;
            } else {
                int letter = current - 'A';
                firstUppercase[letter] = Math.min(firstUppercase[letter], index);
            }
        }

        int answer = 0;
        for (int letter = 0; letter < 26; letter++) {
            if (
                lastLowercase[letter] != -1
                    && firstUppercase[letter] != n
                    && lastLowercase[letter] < firstUppercase[letter]
            ) {
                answer++;
            }
        }

        return answer;
    }
}