Problem Description

You are given a string word that contains letters. A letter c is considered special if it meets two conditions:

1. The letter appears in both lowercase and uppercase forms in the string (e.g., both 'a' and 'A' are present)
2. Every lowercase occurrence of that letter appears before the first uppercase occurrence of the same letter

Your task is to count how many special letters exist in the given string.

For example, if we have a string where 'a' appears at positions 1, 3, 5 and 'A' appears at positions 7, 9, then 'a'/'A' would be special because all lowercase 'a's (positions 1, 3, 5) come before the first uppercase 'A' (position 7).

The solution uses two hash tables to track the first and last occurrences of each character. By comparing the last occurrence of a lowercase letter with the first occurrence of its uppercase counterpart, we can determine if that letter is special. If last[lowercase] < first[uppercase], then all lowercase occurrences must come before the first uppercase occurrence, making it a special letter.

Intuition

To determine if a letter is special, we need to verify that all lowercase occurrences come before any uppercase occurrence. The key insight is that we don't need to track every single occurrence - we only need to know two critical pieces of information:

1. The last position where the lowercase version appears
2. The first position where the uppercase version appears

Why? Because if the last lowercase occurrence is before the first uppercase occurrence, then we can guarantee that ALL lowercase occurrences are before ANY uppercase occurrence.

Think of it this way: imagine we have lowercase 'a' at positions [2, 5, 8] and uppercase 'A' at positions [10, 15]. Instead of checking if 2 < 10, 5 < 10, and 8 < 10, we can simply check if 8 (the last lowercase) < 10 (the first uppercase). If this condition holds true, then all other lowercase positions must also be less than 10.

This observation leads us to use two hash tables:

• first: stores where each character appears for the first time
• last: stores where each character appears for the last time

As we iterate through the string once, we update these positions. Then, for each letter pair (like 'a' and 'A'), we check if last['a'] < first['A']. If both versions exist and this condition is satisfied, we've found a special letter.

This approach is efficient because we reduce the problem from tracking all occurrences to just tracking the boundary positions that matter for our comparison.

Solution Approach

The implementation uses hash tables to track character positions and follows these steps:

1. Initialize two hash tables: Create first and last dictionaries to store the first and last occurrence positions of each character in the string.

2. Single pass through the string: Iterate through word with index i and character c:

   • If character c hasn't been seen before (c not in first), record its position in first[c] = i
   • Always update last[c] = i to track the most recent position of character c

3. Count special letters: Use Python's zip function to pair each lowercase letter with its uppercase counterpart from ascii_lowercase and ascii_uppercase. For each pair (a, b) where a is lowercase and b is uppercase:

   • Check if lowercase a exists in the string: a in last
   • Check if uppercase b exists in the string: b in first
   • Check if all lowercase occurrences come before the first uppercase: last[a] < first[b]
   • If all three conditions are true, this letter is special

4. Return the count: The sum() function counts how many letter pairs satisfy all conditions, giving us the total number of special letters.

The time complexity is O(n + 26) where n is the length of the string (for the initial traversal) and 26 is for checking all letter pairs. The space complexity is O(1) since we store at most 52 character positions (26 lowercase + 26 uppercase).

The elegance of this solution lies in reducing the problem to boundary checking - we only need the last lowercase and first uppercase positions to determine if a letter is special.

Example Walkthrough

Let's walk through the solution with the string word = "aAbBcC".

Step 1: Build the position hash tables

We iterate through the string and track first and last occurrences:

Step 2: Check each letter pair for special condition

Now we check each lowercase/uppercase pair:

Step 3: Count special letters

We found 3 special letters: a/A, b/B, and c/C.

Each satisfies the condition that all lowercase occurrences appear before the first uppercase occurrence.

Another example to illustrate the boundary checking:

Consider word = "aabAAa":

• 'a' appears at positions 0, 1, 5
• 'A' appears at positions 3, 4

After building our hash tables:

• first['a'] = 0, last['a'] = 5
• first['A'] = 3, last['A'] = 4

When checking if 'a'/'A' is special:

• Both 'a' and 'A' exist ✓
• last['a'] < first['A']? → 5 < 3? → False ✗

The letter 'a'/'A' is NOT special because the lowercase 'a' at position 5 comes after the uppercase 'A' at position 3. This demonstrates why tracking just the last lowercase and first uppercase positions is sufficient - if the last lowercase violates the condition, then the letter cannot be special.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + |Σ|)

The algorithm consists of two main parts:

1. A single pass through the string word to build the first and last dictionaries, which takes O(n) time where n is the length of the string.
2. A loop that iterates through the zip of ascii_lowercase and ascii_uppercase, which contains 26 pairs, taking O(26) = O(|Σ|) time where |Σ| represents the size of the character set being checked.

Therefore, the total time complexity is O(n + |Σ|), where in this problem |Σ| = 26 for the English alphabet pairs being checked.

Space Complexity: O(|Σ|)

The space is used by:

1. The first dictionary which stores at most one entry per unique character in the string
2. The last dictionary which stores at most one entry per unique character in the string

Since the string can contain both uppercase and lowercase letters, and we're dealing with ASCII characters, the maximum number of unique characters stored across both dictionaries is bounded by the character set size. In this problem, |Σ| ≤ 52 (26 lowercase + 26 uppercase letters), though the reference mentions |Σ| ≤ 128 considering the full ASCII character set that could appear in the string.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the "before" requirement

A common mistake is checking if any lowercase occurrence comes before any uppercase occurrence, rather than ensuring all lowercase occurrences come before the first uppercase occurrence.

Incorrect approach:

# Wrong: Only checks if first lowercase comes before first uppercase
if first_occurrence[lowercase] < first_occurrence[uppercase]:
    count += 1

Why it fails: Consider the string "aAa". The first 'a' (position 0) comes before 'A' (position 1), but the last 'a' (position 2) comes after 'A', so this letter should NOT be special.

Correct approach:

# Correct: Checks if last lowercase comes before first uppercase
if last_occurrence[lowercase] < first_occurrence[uppercase]:
    count += 1

2. Not handling missing characters properly

Another pitfall is not checking whether both forms (lowercase and uppercase) of a letter actually exist in the string before comparing their positions.

Incorrect approach:

# Wrong: May cause KeyError if character doesn't exist
for lower, upper in zip(ascii_lowercase, ascii_uppercase):
    if last_occurrence[lower] < first_occurrence[upper]:
        count += 1

Correct approach:

# Correct: Checks existence before accessing
for lower, upper in zip(ascii_lowercase, ascii_uppercase):
    if lower in last_occurrence and upper in first_occurrence:
        if last_occurrence[lower] < first_occurrence[upper]:
            count += 1

3. Using wrong comparison for boundary positions

Some might incorrectly use <= instead of < when comparing positions, which would incorrectly count cases where the last lowercase and first uppercase are at the same position (which is impossible for different characters).

Key insight: The solution elegantly reduces the problem to boundary checking - if the rightmost lowercase position is still to the left of the leftmost uppercase position, then ALL lowercase occurrences must be before ALL uppercase occurrences.