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 ofspecial lettersinword.
Example 1:
Input:word = "aaAbcBC"
Output:3
Explanation:
The special characters are 'a', 'b', and 'c'.
Example 2:
Input:word = "abc"
Output:0
Explanation:
There are no special characters in word.
Example 3:
Input:word = "AbBCab"
Output:0
Explanation:
There are no special characters in word.
Constraints:
1 <= word.length <= 2 * 105
word consists of only lowercase and uppercase English letters.
Solutions
Solution 1: Hash Table or Array
We define two hash tables or arrays first and last to store the positions where each letter first appears and last appears respectively.
Then we traverse the string word, updating first and last.
Finally, we traverse all lowercase and uppercase letters. If last[a] exists and first[b] exists and last[a] < first[b], it means that the letter a is a special letter, and we increment the answer by one.
The time complexity is $O(n + |\Sigma|)$, and the space complexity is $O(|\Sigma|)$. Where $n$ is the length of the string word, and $|\Sigma|$ is the size of the character set. In this problem, $|\Sigma| \leq 128$.