Count the Number of Special Characters II — Solution
Count the Number of Special Characters II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count the Number of Special Characters II is a medium coding problem on strings and hash table, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A letter c is special in word if it appears in both cases and every lowercase occurrence of c comes before the first uppercase occurrence of c.
Return the number of special letters in word.
Example 1
Input: word = "aaAbcBC"
Output: 3
Explanation: For `a`, `b` and `c`, all lowercase copies precede the first uppercase copy.
Example 2
Input: word = "abc"
Output: 0
Example 3
Input: word = "AbBCab"
Output: 0
Explanation: `b` has a lowercase copy after `B`, and `a` has one after `A`; `c` never appears in lowercase.
Constraints
1 <= word.length <= 2 * 10^5word consists of only lowercase and uppercase English letters
Hints for Count the Number of Special Characters II
Hint 1
For each letter you only need two positions: the last lowercase occurrence and the first uppercase occurrence.
Hint 2
One pass can record both for all 26 letters.
Hint 3
The letter is special exactly when both positions exist and
lastLower < firstUpper.
How to solve Count the Number of Special Characters II
"Every lowercase before the first uppercase" is the same as "the last lowercase comes before the first uppercase", so two indices per letter decide it.
Approach
- Initialise
lastLower[i] = -1andfirstUpper[i] = -1for all 26 letters. - Scan
wordwith indexj: for a lowercase letter setlastLower = j; for an uppercase letter setfirstUpper = jonly if it is still-1. - Count letters with
lastLower != -1,firstUpper != -1andlastLower < firstUpper.
Why it works
If the latest lowercase copy precedes the earliest uppercase copy, every lowercase copy does; if not, that latest lowercase copy itself breaks the rule. Both occurrences must exist for the letter to appear in both cases.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Overwriting
firstUpperon later uppercase copies turns it into the last uppercase position. - A letter with uppercase copies only (or lowercase only) is not special.
Reference solution
Python
def numberOfSpecialChars(word: str) -> int:
last_lower = [-1] * 26
first_upper = [-1] * 26
for j, c in enumerate(word):
if c.islower():
last_lower[ord(c) - 97] = j
elif first_upper[ord(c) - 65] == -1:
first_upper[ord(c) - 65] = j
return sum(1 for i in range(26)
if last_lower[i] != -1 and first_upper[i] != -1 and last_lower[i] < first_upper[i])Java
public static int numberOfSpecialChars(String word) {
int[] lastLower = new int[26], firstUpper = new int[26];
Arrays.fill(lastLower, -1);
Arrays.fill(firstUpper, -1);
for (int j = 0; j < word.length(); j++) {
char c = word.charAt(j);
if (c >= 'a') lastLower[c - 'a'] = j;
else if (firstUpper[c - 'A'] == -1) firstUpper[c - 'A'] = j;
}
int count = 0;
for (int i = 0; i < 26; i++) {
if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) count++;
}
return count;
}C++
int numberOfSpecialChars(string word) {
vector<int> lastLower(26, -1), firstUpper(26, -1);
for (int j = 0; j < (int) word.size(); j++) {
char c = word[j];
if (c >= 'a') lastLower[c - 'a'] = j;
else if (firstUpper[c - 'A'] == -1) firstUpper[c - 'A'] = j;
}
int count = 0;
for (int i = 0; i < 26; i++) {
if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) count++;
}
return count;
}JavaScript
var numberOfSpecialChars = function(word) {
var lastLower = new Array(26).fill(-1), firstUpper = new Array(26).fill(-1);
for (var j = 0; j < word.length; j++) {
var c = word.charCodeAt(j);
if (c >= 97) lastLower[c - 97] = j;
else if (firstUpper[c - 65] === -1) firstUpper[c - 65] = j;
}
var count = 0;
for (var i = 0; i < 26; i++) {
if (lastLower[i] !== -1 && firstUpper[i] !== -1 && lastLower[i] < firstUpper[i]) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets