Scale Engineer

Count the Number of Special Characters II

Med
#2773Time: O(26 * N) or O(N), where N is the length of the string. For each of the 26 letters, we scan the string (e.g., `indexOf` and `lastIndexOf` each take O(N) time).Space: O(1), as we only use a few variables to store the count and indices, requiring constant extra space.
Data structures
Hash TableString

Prompt

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 of special letters in word.

 

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all 26 possible special characters ('a' through 'z'). For each character, it scans the entire input string to determine if it meets the special character criteria. The core idea is to verify the condition that the last occurrence of the lowercase letter must appear before the first occurrence of its corresponding uppercase letter.

Algorithm

  • Initialize a counter specialCount to 0.
  • Iterate through each character c from 'a' to 'z'.
  • For each c, find the index of its last occurrence in word. Let this be lastLowerIndex.
  • For the same c, find the index of the first occurrence of its uppercase version C. Let this be firstUpperIndex.
  • To find these indices, you can either use built-in string functions like lastIndexOf() and indexOf() or manually iterate through the string.
  • Check if both characters were found (i.e., their indices are not -1).
  • If both are found and lastLowerIndex < firstUpperIndex, it means all lowercase occurrences appear before the first uppercase one. Increment specialCount.
  • After checking all 26 letters of the alphabet, return specialCount.

Walkthrough

The algorithm checks each of the 26 lowercase English letters one by one. For a letter, say c, we need to verify two conditions:

  1. Both its lowercase (c) and uppercase (C) forms exist in the string word.
  2. Every occurrence of c appears before the first occurrence of C. This is equivalent to checking if the last occurrence of c is before the first occurrence of C.

To implement this, for each character from 'a' to 'z': a. Find the index of the last occurrence of the lowercase letter using word.lastIndexOf(c). b. Find the index of the first occurrence of the uppercase letter using word.indexOf(C). c. If both letters are found (indices are not -1) and the last lowercase index is less than the first uppercase index, we count it as a special character. The total count is returned after checking all 26 letters.

class Solution {    public int numberOfSpecialChars(String word) {        int specialCount = 0;        for (char c = 'a'; c <= 'z'; c++) {            char upperC = Character.toUpperCase(c);                        int lastLower = word.lastIndexOf(c);            int firstUpper = word.indexOf(upperC);             if (lastLower != -1 && firstUpper != -1 && lastLower < firstUpper) {                specialCount++;            }        }        return specialCount;    }}

Complexity

Time

O(26 * N) or O(N), where N is the length of the string. For each of the 26 letters, we scan the string (e.g., `indexOf` and `lastIndexOf` each take O(N) time).

Space

O(1), as we only use a few variables to store the count and indices, requiring constant extra space.

Trade-offs

Pros

  • The logic is straightforward and directly translates the problem's conditions.

  • It's easy to implement using built-in string manipulation functions.

Cons

  • This approach repeatedly scans the input string for each of the 26 characters, which is less efficient than a single-pass solution.

  • For a long string, the total number of operations can be significantly higher than in an optimized approach, even though the Big O notation is the same.

Solutions

class Solution {public  int numberOfSpecialChars(String word) {    int[] first = new int['z' + 1];    int[] last = new int['z' + 1];    for (int i = 1; i <= word.length(); ++i) {      int j = word.charAt(i - 1);      if (first[j] == 0) {        first[j] = i;      }      last[j] = i;    }    int ans = 0;    for (int i = 0; i < 26; ++i) {      if (last['a' + i] > 0 && first['A' + i] > 0 &&          last['a' + i] < first['A' + i]) {        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem