Scale Engineer

Count the Number of Special Characters I

Easy
#2772Time: O(26 * N) or simply O(N), where N is the length of the `word`. The outer loop runs a constant 26 times, and for each iteration, the inner loop scans the entire string of length N.Space: O(1), as we only use a few variables to store the count and flags, regardless of the input string's size.
Data structures
Hash TableString

Prompt

You are given a string word. A letter is called special if it appears both in lowercase and uppercase in word.

Return the number of special letters in word.

 

Example 1:

Input: word = "aaAbcBC"

Output: 3

Explanation:

The special characters in word are 'a', 'b', and 'c'.

Example 2:

Input: word = "abc"

Output: 0

Explanation:

No character in word appears in uppercase.

Example 3:

Input: word = "abBCab"

Output: 1

Explanation:

The only special character in word is 'b'.

 

Constraints:

  • 1 <= word.length <= 50
  • word consists of only lowercase and uppercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each letter of the English alphabet from 'a' to 'z'. For each letter, it checks if both its lowercase and uppercase versions are present in the input string word by performing a full scan of the string for each letter.

Algorithm

  • Initialize a counter specialCount to 0.
  • Loop through each character c from 'a' to 'z'.
  • Inside the loop, determine the uppercase equivalent upperC.
  • Use two boolean flags, foundLower and foundUpper, initialized to false.
  • Iterate through the entire word to check for the presence of c and upperC.
  • If a character in word matches c, set foundLower to true.
  • If a character in word matches upperC, set foundUpper to true.
  • After checking the whole string, if both foundLower and foundUpper are true, it means the character is special, so we increment specialCount.
  • After the outer loop finishes, specialCount will hold the total number of special characters.

Walkthrough

The brute-force method systematically checks for each of the 26 possible special characters. It loops from 'a' to 'z', and for each letter, it scans the entire input string word to see if both the lowercase and corresponding uppercase forms exist. Two boolean flags, foundLower and foundUpper, are used within this loop to track their presence. If, after a full scan, both flags are true, a special character has been found, and a counter is incremented. While simple, this method is not optimal because the string is traversed multiple times.

class Solution {    public int numberOfSpecialChars(String word) {        int specialCount = 0;        for (char c = 'a'; c <= 'z'; c++) {            char upperC = Character.toUpperCase(c);            boolean foundLower = false;            boolean foundUpper = false;            for (int i = 0; i < word.length(); i++) {                if (word.charAt(i) == c) {                    foundLower = true;                }                if (word.charAt(i) == upperC) {                    foundUpper = true;                }            }            if (foundLower && foundUpper) {                specialCount++;            }        }        return specialCount;    }}

Complexity

Time

O(26 * N) or simply O(N), where N is the length of the `word`. The outer loop runs a constant 26 times, and for each iteration, the inner loop scans the entire string of length N.

Space

O(1), as we only use a few variables to store the count and flags, regardless of the input string's size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space apart from a few variables.

Cons

  • Inefficient as it repeatedly scans the input string for each letter of the alphabet, leading to a higher constant factor in its time complexity compared to single-pass solutions.

Solutions

class Solution {public  int numberOfSpecialChars(String word) {    boolean[] s = new boolean['z' + 1];    for (int i = 0; i < word.length(); ++i) {      s[word.charAt(i)] = true;    }    int ans = 0;    for (int i = 0; i < 26; ++i) {      if (s['a' + i] && s['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