3120. Count the Number of Special Characters I

Time: O(n + 26)

Space: O(26)

Intuition

Each alphabet letter can appear in lowercase, uppercase, both, or neither. In this variant, a letter is special only if the lowercase occurrence appears before the uppercase occurrence. So we need both presence tracking and order awareness, not just counts.

Algorithm

1Create two boolean arrays of size 26: lower[] and upper[].
2Traverse each character c in word:
3 If c is lowercase, mark lower[c - "a"] only if the uppercase version has not been seen yet.
4 Otherwise mark upper[c - "A"] = true.
5After traversal, iterate i from 0 to 25 and count positions where lower[i] && upper[i].
6Return the count.

Example Walkthrough

Input: word = "aaAbcBC"

1.For a: lowercase appears before uppercase A, so a is special.
2.For b and c: lowercase appears before uppercase B/C, so both are special.
3.Total special characters = 3.

Output: 3

Common Pitfalls

•Order matters in variant II; a lowercase after the uppercase should not count.
•Use separate arrays (or sets) for lowercase and uppercase to avoid accidental index mixing.
•Do not count a letter just because both cases appear somewhere; the lowercase must come first.

3120.cs

// Approach: Track whether each lowercase and uppercase letter appears using two boolean arrays.
// A letter is special if both its lowercase and uppercase forms are present in the word.
// Count such letters across all 26 alphabet positions.
// Time: O(n + 26) Space: O(26)

public class Solution
{
    public int NumberOfSpecialChars(string word)
    {
        int ans = 0;
        bool[] lower = new bool[26];
        bool[] upper = new bool[26];

        foreach (char c in word)
        {
            if (char.IsLower(c))
                lower[c - 'a'] = true;
            else
                upper[c - 'A'] = true;
        }

        for (int i = 0; i < 26; ++i)
        {
            if (lower[i] && upper[i])
                ++ans;
        }

        return ans;
    }
}

Was this solution helpful?