We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Special Characters II

Difficulty: Medium

Problem Description

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.

Key Insights

  • A letter is special if it exists in both cases (lowercase and uppercase).
  • All occurrences of the lowercase version must appear before any occurrence of the uppercase version.
  • We can use a hash table to track the lowercase and uppercase occurrences of each character efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (constant space for the hash table since it only contains a limited number of characters)

Solution

We will iterate through the string while using a hash table to keep track of the state of each character (whether we've seen lowercase or uppercase). For each character encountered:

  1. If it's lowercase, we mark it as seen in lowercase.
  2. If it's uppercase, we check if the corresponding lowercase has been seen and that no lowercase has been seen after this uppercase.
  3. At the end of the iteration, we count how many letters are special based on the collected data.

Code Solutions

def countSpecialCharacters(word: str) -> int:
    # Dictionary to track the state of each character
    seen = {}
    special_count = 0
    
    for char in word:
        if char.islower():
            # Mark the lowercase character as seen
            seen[char] = seen.get(char, 0) | 1  # 1 indicates lowercase seen
        elif char.isupper():
            lower_char = char.lower()
            # Check if the lowercase has been seen and mark the uppercase as seen
            if lower_char in seen and seen[lower_char] == 1:
                seen[lower_char] = 2  # 2 indicates both lowercase and uppercase seen
                special_count += 1
    
    return special_count
← Back to All Questions