3121. Count the Number of Special Characters II

3121. Count the Number of Special Characters II

Difficulty: Medium

Topics: Senior, Hash Table, String, Weekly Contest 394

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: "AbBCab"
Output: [0,1]
Explanation: There are no special characters in word.

Constraints:

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

Hint:

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

Solution:

The problem requires counting letters that appear in both lowercase and uppercase forms in a string, with the constraint that every lowercase occurrence of a letter must appear before the first uppercase occurrence of the same letter.

The solution tracks the first occurrence of each uppercase letter and the last occurrence of each lowercase letter, then compares their indices.

Approach:

• Use two arrays to store the first occurrence index of uppercase letters and the last occurrence index of lowercase letters.
• Iterate through the string once, updating these arrays.
• For each letter a..z, check if:
  • Both its lowercase and uppercase forms exist in the string.
  • The last lowercase occurrence occurs before the first uppercase occurrence.
• If both conditions are met, count it as a special character.

Let's implement this solution in PHP: 3121. Count the Number of Special Characters II

<?php
/**
 * @param String $word
 * @return Integer
 */
function numberOfSpecialChars(string $word): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo numberOfSpecialChars("aaAbcBC") . "\n";        // Output: 3
echo numberOfSpecialChars("abc") . "\n";            // Output: 0
echo numberOfSpecialChars("AbBCab") . "\n";         // Output: 0
?>

Explanation:

• first array stores the first occurrence index for each character (both cases).
• last array stores the last occurrence index for each character.
• During traversal:
  • If a character hasn’t been seen before, set first[char] to current index.
  • Always update last[char] to current index.
• After traversal, check each lowercase letter i:
  • last['a' + i] → last index of lowercase.
  • first['A' + i] → first index of uppercase.
  • Condition: last[lower] < first[upper] ensures all lowercase occur before any uppercase.
• Count how many satisfy this.

Complexity

• Time Complexity: O(n) — single pass through the string, then O(26) for checking letters.
• Space Complexity: O(1) — fixed-size arrays for ASCII characters.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub