3121. Count the Number of Special Characters II

Description

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: Hash Table

• Time complexity: O(26+n)
• Space complexity: O(26 -> 1)

 

JavaScript

/**
 * @param {string} word
 * @return {number}
 */
const numberOfSpecialChars = function (word) {
  const n = word.length;
  const LOWER_CODE_A = 'a'.charCodeAt(0);
  const UPPER_CODE_A = 'A'.charCodeAt(0);
  const uppercaseFirst = Array.from({ length: 26 }, () => -1);
  const lowercaseLast = Array.from({ length: 26 }, () => -1);
  let result = 0;

  for (let index = 0; index < n; index++) {
    const char = word[index];

    if (/[a-z]/.test(char)) {
      const code = char.charCodeAt(0) - LOWER_CODE_A;

      lowercaseLast[code] = index;
    } else {
      const code = char.charCodeAt(0) - UPPER_CODE_A;

      if (uppercaseFirst[code] === -1) {
        uppercaseFirst[code] = index;
      }
    }
  }

  for (let code = 0; code < 26; code++) {
    if (lowercaseLast[code] === -1) continue;

    if (lowercaseLast[code] < uppercaseFirst[code]) {
      result += 1;
    }
  }

  return result;
};