LeetCode 3121 - Count the Number of Special Characters II

The problem gives us a string word containing uppercase and lowercase English letters. We must count how many letters are considered "special". A character c is special if two conditions are true: 1. The lowercase version of the letter appears somewhere in the string. 2.

leetcodemediumhash-tablestring

LeetCode Problem 3121

Difficulty: 🟡 Medium
Topics: Hash Table, String

Solution

Problem Understanding

The problem gives us a string word containing uppercase and lowercase English letters. We must count how many letters are considered "special".

A character c is special if two conditions are true:

  1. The lowercase version of the letter appears somewhere in the string.
  2. The uppercase version of the same letter also appears somewhere in the string.
  3. Every lowercase occurrence appears before the first uppercase occurrence.

The third condition is the important part. It is not enough for both cases to exist. The ordering must also be valid.

For example, in "aaAbcBC":

  • 'a' appears as lowercase before 'A', so it is special.
  • 'b' appears as lowercase before 'B', so it is special.
  • 'c' appears as lowercase before 'C', so it is special.

The answer is 3.

However, consider "AbBCab":

  • Lowercase 'a' appears after uppercase 'A'.
  • Lowercase 'b' appears after uppercase 'B'.

Even though both lowercase and uppercase versions exist, the ordering rule is violated, so the answer is 0.

The input length can be as large as 2 * 10^5, which means we need an efficient solution. Any algorithm worse than linear or near linear time could become too slow.

An important observation is that there are only 26 English letters. This allows us to track information for each character very efficiently.

Several edge cases are important:

  • A letter may appear only in lowercase or only in uppercase.
  • A lowercase letter appearing after an uppercase occurrence invalidates that character permanently.
  • Multiple lowercase occurrences before uppercase are allowed.
  • Multiple uppercase occurrences after lowercase are also allowed.
  • A string with repeated mixed ordering such as "aAa" is invalid for 'a' because a lowercase occurrence appears after the first uppercase occurrence.

Approaches

Brute Force Approach

A straightforward solution is to process each letter from 'a' to 'z' independently.

For every character:

  1. Scan the string to find all lowercase positions.
  2. Scan again to find all uppercase positions.
  3. Verify:
  • Both forms exist.
  • The maximum lowercase index is smaller than the minimum uppercase index.

If these conditions hold, the letter is special.

This approach is correct because it directly checks the definition of a special character. However, it repeatedly scans the string for every letter.

Since there are 26 letters, and each scan takes O(n) time, the overall complexity becomes O(26 * n). Technically this is still linear because 26 is constant, but we can do better conceptually with a cleaner single-pass approach.

Optimal Approach

The key insight is that we only care about the relative ordering between lowercase and uppercase appearances for each letter.

We can process the string once from left to right and maintain the state of each letter.

For each character:

  • If it is lowercase:

  • If we have already seen its uppercase version, then this letter becomes invalid permanently.

  • Otherwise, mark that lowercase has appeared.

  • If it is uppercase:

  • If lowercase appeared before and the letter is not invalid, then it becomes special.

  • Mark uppercase as seen.

This works because the moment a lowercase letter appears after an uppercase one, the ordering rule is broken forever.

Since there are only 26 letters, we can use arrays of size 26 for constant-time operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(26 × n) O(1) Checks each letter separately
Optimal O(n) O(1) Single pass with state tracking

Algorithm Walkthrough

  1. Create three arrays of size 26:
  • seen_lower, tracks whether a lowercase version has appeared.
  • seen_upper, tracks whether an uppercase version has appeared.
  • invalid, tracks whether the ordering rule has been violated.
  1. Iterate through the string character by character.
  2. If the current character is lowercase:
  • Convert it into an index from 0 to 25.
  • If its uppercase version has already appeared, then a lowercase character is appearing too late, so mark this letter as invalid.
  • Mark the lowercase version as seen.
  1. If the current character is uppercase:
  • Convert it into the corresponding index.
  • Mark the uppercase version as seen.
  1. After processing the entire string, iterate through all 26 letters.
  2. A letter is special if:
  • Lowercase appeared.
  • Uppercase appeared.
  • The letter is not invalid.
  1. Count all such letters and return the result.

Why it works

The algorithm maintains a simple invariant:

  • A letter remains valid only if no lowercase occurrence appears after an uppercase occurrence.

The moment we encounter a lowercase character after seeing its uppercase form, we permanently mark the letter as invalid. Since we process the string from left to right, this correctly captures the ordering requirement from the problem statement.

At the end, every valid letter with both lowercase and uppercase appearances satisfies the definition of a special character.

Python Solution

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        seen_lower = [False] * 26
        seen_upper = [False] * 26
        invalid = [False] * 26

        for ch in word:
            if ch.islower():
                index = ord(ch) - ord('a')

                if seen_upper[index]:
                    invalid[index] = True

                seen_lower[index] = True
            else:
                index = ord(ch) - ord('A')
                seen_upper[index] = True

        result = 0

        for i in range(26):
            if seen_lower[i] and seen_upper[i] and not invalid[i]:
                result += 1

        return result

The implementation uses three fixed-size arrays because there are only 26 English letters.

During the scan:

  • seen_lower[index] records whether the lowercase character has appeared.
  • seen_upper[index] records whether the uppercase character has appeared.
  • invalid[index] becomes True if a lowercase occurrence appears after an uppercase occurrence.

The final loop checks which letters satisfy all required conditions.

This solution performs a single pass through the string and uses constant extra memory.

Go Solution

func numberOfSpecialChars(word string) int {
    seenLower := make([]bool, 26)
    seenUpper := make([]bool, 26)
    invalid := make([]bool, 26)

    for _, ch := range word {
        if ch >= 'a' && ch <= 'z' {
            index := ch - 'a'

            if seenUpper[index] {
                invalid[index] = true
            }

            seenLower[index] = true
        } else {
            index := ch - 'A'
            seenUpper[index] = true
        }
    }

    result := 0

    for i := 0; i < 26; i++ {
        if seenLower[i] && seenUpper[i] && !invalid[i] {
            result++
        }
    }

    return result
}

The Go solution follows exactly the same logic as the Python version.

Instead of Python lists, Go uses boolean slices of length 26. Character arithmetic is performed using rune subtraction, which naturally converts letters into indices from 0 to 25.

There are no integer overflow concerns because all values remain very small.

Worked Examples

Example 1

Input:

word = "aaAbcBC"

Processing steps:

Character Action seen_lower seen_upper invalid
a lowercase seen a none none
a lowercase seen a none none
A uppercase seen a a none
b lowercase seen a,b a none
c lowercase seen a,b,c a none
B uppercase seen a,b,c a,b none
C uppercase seen a,b,c a,b,c none

Final valid letters:

  • a
  • b
  • c

Answer:

3

Example 2

Input:

word = "abc"

Processing:

Character Action
a lowercase only
b lowercase only
c lowercase only

No uppercase versions exist.

Answer:

0

Example 3

Input:

word = "AbBCab"

Processing steps:

Character Action invalid letters
A uppercase seen none
b lowercase seen none
B uppercase seen none
C uppercase seen none
a lowercase after uppercase A a
b lowercase after uppercase B a,b

Both 'a' and 'b' become invalid because lowercase appears after uppercase.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the string
Space O(1) Arrays of fixed size 26

The algorithm processes each character exactly once, so the running time grows linearly with the string length.

The extra memory usage remains constant because the arrays always store information for only 26 letters, regardless of input size.

Test Cases

solution = Solution()

assert solution.numberOfSpecialChars("aaAbcBC") == 3  # standard valid example
assert solution.numberOfSpecialChars("abc") == 0  # no uppercase letters
assert solution.numberOfSpecialChars("AbBCab") == 0  # lowercase appears after uppercase
assert solution.numberOfSpecialChars("aA") == 1  # simplest valid case
assert solution.numberOfSpecialChars("Aa") == 0  # invalid ordering
assert solution.numberOfSpecialChars("aAa") == 0  # lowercase after uppercase invalidates
assert solution.numberOfSpecialChars("abcABC") == 3  # all letters valid
assert solution.numberOfSpecialChars("ABCabc") == 0  # all invalid ordering
assert solution.numberOfSpecialChars("aabbccAABBCC") == 3  # multiple occurrences
assert solution.numberOfSpecialChars("aAbBcC") == 3  # alternating valid pairs
assert solution.numberOfSpecialChars("aABb") == 1  # only 'a' valid
assert solution.numberOfSpecialChars("zZ") == 1  # edge alphabet letter
assert solution.numberOfSpecialChars("zzZZ") == 1  # repeated valid occurrences
assert solution.numberOfSpecialChars("ZZzz") == 0  # repeated invalid occurrences
assert solution.numberOfSpecialChars("m") == 0  # single lowercase
assert solution.numberOfSpecialChars("M") == 0  # single uppercase
Test Why
"aaAbcBC" Basic mixed valid example
"abc" No uppercase letters
"AbBCab" Invalid due to ordering
"aA" Smallest valid case
"Aa" Smallest invalid case
"aAa" Lowercase after uppercase
"abcABC" All letters valid
"ABCabc" All letters invalid
"aabbccAABBCC" Multiple repeated characters
"aAbBcC" Independent valid pairs
"aABb" Mixed valid and invalid
"zZ" Boundary alphabet character
"zzZZ" Repeated valid sequence
"ZZzz" Repeated invalid sequence
"m" Single lowercase character
"M" Single uppercase character

Edge Cases

Lowercase Appears After Uppercase

A case like "aAa" is particularly important. A naive implementation might see lowercase and uppercase versions and incorrectly count the letter as special.

The correct behavior is to reject the letter because the final lowercase 'a' appears after 'A'.

The implementation handles this by marking the letter as invalid immediately when a lowercase character appears after an uppercase occurrence.

Only One Case Exists

Strings like "abc" or "ABC" contain only lowercase or only uppercase letters.

A valid special character requires both forms to appear. The algorithm explicitly checks that both seen_lower and seen_upper are true before counting a letter.

Multiple Valid Occurrences

A string such as "aaabbbAAABBB" should still count both 'a' and 'b' as special.

The rule does not require only one occurrence. It only requires that every lowercase occurrence comes before the first uppercase occurrence.

The implementation naturally supports this because lowercase letters appearing before uppercase do not invalidate the character, regardless of repetition.