Count the Number of Special Characters II

Medium
1815.

Count the Number of Special Characters II

Count the Number of Special Characters II is a medium coding problem on strings and hash table, asked in Amazon interviews.

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^5
  • word consists of only lowercase and uppercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var numberOfSpecialChars = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • word consists of only lowercase and uppercase English letters

Hints for Count the Number of Special Characters II

  1. Hint 1

    For each letter you only need two positions: the last lowercase occurrence and the first uppercase occurrence.

  2. Hint 2

    One pass can record both for all 26 letters.

  3. 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

  1. Initialise lastLower[i] = -1 and firstUpper[i] = -1 for all 26 letters.
  2. Scan word with index j: for a lowercase letter set lastLower = j; for an uppercase letter set firstUpper = j only if it is still -1.
  3. Count letters with lastLower != -1, firstUpper != -1 and lastLower < 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 firstUpper on 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