LeetCode Solutions Blog

Count the Number of Special Characters II

Number: 3405

Difficulty: Medium

Paid? No

Problem Description

Given a string word, a letter c is called special if it appears in both lowercase and uppercase in word, and every lowercase occurrence of c appears before the first uppercase occurrence of c. The task is to count the number of special letters in word.

Key Insights

A letter is only special if it appears in both lowercase and uppercase forms.
The order is crucial: All occurrences of the lowercase letter must occur before its first uppercase occurrence.
By tracking the first appearance of an uppercase letter and the last appearance of the lowercase letter for each character, we can determine if the condition is satisfied.
Since there are only 26 letters, iterating through each letter and checking conditions keeps the solution efficient.

Space and Time Complexity

Time Complexity: O(n) – we traverse the string once, and then iterate over 26 letters. Space Complexity: O(1) – we store only a constant amount of information for each letter.

Solution

We solve the problem by iterating through the string and tracking for each letter:

The index of the first uppercase occurrence.
The index of the last lowercase occurrence. For each letter from 'a' to 'z', if both forms exist and the last lowercase index is less than the first uppercase index, then the letter is special. This approach uses simple arrays (or dictionaries) for tracking indices and checks a single condition per letter.

Code Solutions

# Python solution with line-by-line comments
def countSpecialCharacters(word):
    # Create a dictionary to store the first uppercase index for each letter.
    first_upper = {}
    # Create a dictionary to store the last lowercase index for each letter.
    last_lower = {}

    # Loop through word with index
    for i, ch in enumerate(word):
        # Check if current character is lowercase.
        if ch.islower():
            # Update the last seen index for lowercase letter.
            # Use ch directly as key.
            last_lower[ch] = i
        else:
            # Convert uppercase letter to lowercase key.
            key = ch.lower()
            # If this is the first uppercase occurrence, record its index.
            if key not in first_upper:
                first_upper[key] = i

    # Initialize counter for special characters.
    count = 0
    # Iterate over each letter in alphabet.
    for ch in 'abcdefghijklmnopqrstuvwxyz':
        # Check if both uppercase and lowercase occurrences exist.
        if ch in last_lower and ch in first_upper:
            # If every lowercase occurrence (tracked by last_lower index)
            # occurs before the first uppercase occurrence, it's special.
            if last_lower[ch] < first_upper[ch]:
                count += 1

    return count

# Example usage:
print(countSpecialCharacters("aaAbcBC"))  # Output should be 3