Problem Statement in English

You’re given a string word consisting of lowercase and uppercase English letters. A character is called special if both the lowercase and uppercase version of it exist in the string and every lowercase instance of it appears before the first uppercase instance of it in the string.

Approach

This is purely an implementation problem. We can use a dictionary to store the position of the first occurrence of each character in the string. We can also use another dictionary to store the mapping of lowercase characters to their corresponding uppercase characters.

Then, we can iterate through the alphabet and check if both the lowercase and uppercase versions of a character exist in the string and if the position of the lowercase version is less than the position of the uppercase version. If it is, then we can increment our result counter.

And we’re done!

Solution in Python


class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        dual = {}

        for i in range(26):
            dual[chr(ord('a') + i)] = chr(ord('A') + i)

        pos = {}

        for i, c in enumerate(word):
            if c in dual: pos[c] = i
            if c in pos: continue
            pos[c] = i

        res = 0

        for i in range(26):
            smaller = chr(ord('a') + i)

            if smaller in pos and dual[smaller] in pos and pos[smaller] < pos[dual[smaller]]:
                res += 1

        return res

Complexity

  • Time: $O(n)$
    Since we need to iterate through the string once to build the pos dictionary and then iterate through the alphabet to count the number of special characters.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space to store the dual and pos dictionaries, which have a maximum size of 26.

And we are done.