Count the Number of Special Characters II

medium hash table string indexing

Problem

Given a string word, a letter c is special if it appears in both lowercase and uppercase, and every lowercase occurrence of c appears before the first uppercase occurrence of c. Return how many letters are special.

Equivalently, a letter is special when the last index of its lowercase form is less than the first index of its uppercase form (and both forms appear).

Inputword = "aaAbcBC"

Output3

The special letters are 'a', 'b', and 'c': each lowercase run finishes before its uppercase appears.

word (letters only)

def numberOfSpecialChars(word):
    first_upper = {}          # letter -> first index seen uppercase
    last_lower = {}           # letter -> last index seen lowercase
    for i, ch in enumerate(word):
        if ch.islower():
            last_lower[ch] = i             # always overwrite: keep latest
        else:
            low = ch.lower()
            if low not in first_upper:
                first_upper[low] = i       # only the first uppercase index
    count = 0
    for c in last_lower:
        # special: lowercase exists, uppercase exists, all lowers come first
        if c in first_upper and last_lower[c] < first_upper[c]:
            count += 1
    return count

function numberOfSpecialChars(word) {
  const firstUpper = {};            // letter -> first uppercase index
  const lastLower = {};             // letter -> last lowercase index
  for (let i = 0; i < word.length; i++) {
    const ch = word[i];
    if (ch >= "a" && ch <= "z") {
      lastLower[ch] = i;            // overwrite: keep latest lowercase
    } else {
      const low = ch.toLowerCase();
      if (!(low in firstUpper)) firstUpper[low] = i; // first uppercase only
    }
  }
  let count = 0;
  for (const c in lastLower) {
    // all lowers before first upper, and both forms present
    if (c in firstUpper && lastLower[c] < firstUpper[c]) count++;
  }
  return count;
}

int numberOfSpecialChars(String word) {
    int[] firstUpper = new int[26];   // first uppercase index, -1 if none
    int[] lastLower = new int[26];    // last lowercase index, -1 if none
    Arrays.fill(firstUpper, -1);
    Arrays.fill(lastLower, -1);
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        if (ch >= 'a' && ch <= 'z') {
            lastLower[ch - 'a'] = i;              // keep latest lowercase
        } else if (firstUpper[ch - 'A'] == -1) {
            firstUpper[ch - 'A'] = i;            // first uppercase only
        }
    }
    int count = 0;
    for (int c = 0; c < 26; c++) {
        // both forms present and all lowers before first upper
        if (lastLower[c] != -1 && firstUpper[c] != -1 && lastLower[c] < firstUpper[c]) count++;
    }
    return count;
}

int numberOfSpecialChars(string word) {
    vector<int> firstUpper(26, -1);   // first uppercase index, -1 if none
    vector<int> lastLower(26, -1);    // last lowercase index, -1 if none
    for (int i = 0; i < (int)word.size(); i++) {
        char ch = word[i];
        if (ch >= 'a' && ch <= 'z') {
            lastLower[ch - 'a'] = i;             // keep latest lowercase
        } else if (firstUpper[ch - 'A'] == -1) {
            firstUpper[ch - 'A'] = i;           // first uppercase only
        }
    }
    int count = 0;
    for (int c = 0; c < 26; c++) {
        // both forms present and all lowers before first upper
        if (lastLower[c] != -1 && firstUpper[c] != -1 && lastLower[c] < firstUpper[c]) count++;
    }
    return count;
}

Explanation

A letter is special when it shows up in both cases and the rule "all lowercase before any uppercase" holds. The tricky part is the ordering condition, but it collapses into a single comparison.

For a fixed letter, "every lowercase occurrence appears before the first uppercase occurrence" is exactly the same as saying the last lowercase index is smaller than the first uppercase index. If the latest lowercase already comes earlier than the earliest uppercase, then every lowercase does.

So we sweep the string once and fill two maps: last_lower[c] is overwritten on every lowercase hit (so it ends as the latest one), and first_upper[c] is written only the first time we see the uppercase form. Both are O(1) per character.

Finally we walk the 26 letters (or the keys of the lowercase map). A letter counts when it has a lowercase index, has an uppercase index, and last_lower[c] < first_upper[c].

Example: "aaAbcBC". For 'a', last lowercase is index 1, first uppercase is index 2 → special. For 'b', last lowercase index 3, first uppercase index 5 → special. For 'c', last lowercase index 4, first uppercase index 6 → special. Total = 3.

Time: O(n) Space: O(1) (26 letters)