Count the Number of Special Characters I
EasyPrompt
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 <= 50wordconsists 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
specialCountto 0. - Loop through each character
cfrom 'a' to 'z'. - Inside the loop, determine the uppercase equivalent
upperC. - Use two boolean flags,
foundLowerandfoundUpper, initialized tofalse. - Iterate through the entire
wordto check for the presence ofcandupperC. - If a character in
wordmatchesc, setfoundLowertotrue. - If a character in
wordmatchesupperC, setfoundUppertotrue. - After checking the whole string, if both
foundLowerandfoundUpperaretrue, it means the character is special, so we incrementspecialCount. - After the outer loop finishes,
specialCountwill 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.
This approach improves upon the brute-force method by avoiding repeated traversals of the string. It uses two hash sets to store the unique lowercase and uppercase characters present in the word in a single pass. Then, it checks for matches between the two sets.
Algorithm
- Create two
HashSet<Character>: one for lowercase letters (lowerSet) and one for uppercase letters (upperSet). - Iterate through the input
wordjust once. - For each character
chin the word:- If
chis a lowercase letter, add it tolowerSet. - If
chis an uppercase letter, add it toupperSet.
- If
- After populating the sets, initialize a counter
specialCountto 0. - Iterate through
lowerSet. - For each lowercase character
lcinlowerSet, check if its uppercase versionCharacter.toUpperCase(lc)exists inupperSet. - If the uppercase version is found, increment
specialCount. - Finally, return
specialCount.
Walkthrough
To make the process more efficient, we can first collect all unique lowercase and uppercase characters from the word. Two hash sets are ideal for this, as they automatically handle uniqueness. We iterate through the word once, placing lowercase characters into a lowerSet and uppercase characters into an upperSet. After this single pass, we have two sets containing all the unique letters of each case. Then, we can iterate through one of the sets (e.g., the lowerSet) and for each character, check for the existence of its opposite-case counterpart in the other set. Since hash set lookups take constant time on average, this second step is very fast. This method reduces the overall time complexity by eliminating the need for multiple scans of the input string.
import java.util.HashSet;import java.util.Set; class Solution { public int numberOfSpecialChars(String word) { Set<Character> lowerSet = new HashSet<>(); Set<Character> upperSet = new HashSet<>(); for (char ch : word.toCharArray()) { if (Character.isLowerCase(ch)) { lowerSet.add(ch); } else if (Character.isUpperCase(ch)) { upperSet.add(ch); } } int specialCount = 0; for (char lowerChar : lowerSet) { if (upperSet.contains(Character.toUpperCase(lowerChar))) { specialCount++; } } return specialCount; }}Complexity
Time
O(N), where N is the length of the `word`. The first loop to populate the sets takes O(N) time. The second loop runs at most 26 times, and each check is O(1) on average. Thus, the total time is dominated by the initial pass over the string.
Space
O(K), where K is the number of unique characters in the alphabet (K=26). Since the alphabet size is fixed, this is considered O(1) constant space.
Trade-offs
Pros
More efficient than brute force as it only requires a single pass over the input string.
Conceptually clean and easy to reason about.
Cons
Has a slight overhead due to using hash sets (hashing, potential collisions) compared to a direct array-based approach.
Uses more space than the brute-force approach, although the space is constant.
This is the most efficient approach. It uses two boolean arrays as direct-addressing tables to track the presence of lowercase and uppercase letters. This avoids the overhead of hashing associated with hash sets and provides the fastest performance.
Algorithm
- Create two boolean arrays of size 26,
lowerPresentandupperPresent, and initialize all their elements tofalse. - Iterate through the
wordonce. - For each character
ch:- If
chis a lowercase letter, calculate its index (ch - 'a') and setlowerPresent[ch - 'a'] = true. - If
chis an uppercase letter, calculate its index (ch - 'A') and setupperPresent[ch - 'A'] = true.
- If
- After the pass is complete, initialize a counter
specialCountto 0. - Iterate from
i = 0to25. - For each index
i, if bothlowerPresent[i]andupperPresent[i]aretrue, incrementspecialCount. - Return
specialCount.
Walkthrough
This optimal solution leverages the fact that the input consists of only English letters. We can use two boolean arrays, lowerPresent and upperPresent, each of size 26, to act as a checklist for the alphabet. We traverse the input word a single time. For each character, we determine if it's lowercase or uppercase and update the corresponding array. For a lowercase character c, we mark lowerPresent[c - 'a'] as true. For an uppercase character C, we mark upperPresent[C - 'A'] as true. After this O(N) pass, we simply iterate through the 26 indices of the arrays. If lowerPresent[i] and upperPresent[i] are both true for any index i, it signifies a special character. This final check takes a constant O(26) time. This method is faster than using hash sets because array indexing is a direct, constant-time operation with no computational overhead for hashing or collision resolution.
class Solution { public int numberOfSpecialChars(String word) { boolean[] lowerPresent = new boolean[26]; boolean[] upperPresent = new boolean[26]; for (char ch : word.toCharArray()) { if (ch >= 'a' && ch <= 'z') { lowerPresent[ch - 'a'] = true; } else if (ch >= 'A' && ch <= 'Z') { upperPresent[ch - 'A'] = true; } } int specialCount = 0; for (int i = 0; i < 26; i++) { if (lowerPresent[i] && upperPresent[i]) { specialCount++; } } return specialCount; }}Complexity
Time
O(N), where N is the length of the `word`. We perform one pass over the string (O(N)) and one pass over the arrays (O(26), which is O(1)). The total time is O(N).
Space
O(1). We use two fixed-size arrays of size 26, which is constant space that does not depend on the input size.
Trade-offs
Pros
Highly efficient with minimal overhead due to direct array access.
Optimal time and space complexity for the given constraints.
Requires only a single pass over the input string.
Cons
This approach is specifically tailored to the English alphabet and would need modification for a larger character set.
Solutions
Solution
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; }}class Solution {public: int numberOfSpecialChars(string word) { vector<bool> s('z' + 1); for (char &c : word) { s[c] = true; } int ans = 0; for (int i = 0; i < 26; ++i) { ans += s['a' + i] && s['A' + i]; } return ans; }};class Solution: def numberOfSpecialChars(self, word: str) -> int: s = set(word) return sum(a in s and b in s for a, b in zip(ascii_lowercase, ascii_uppercase))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.