Count the Number of Special Characters I solution and explanation
Google
9 more videos on this problem
3121 & 3120 Count the Number of Special Characters II & Characters IAryan Mittal · 14:54 · 3K views
Count the Number of Special Characters I | Leetcode - 3120Shivam Gupta · 7:24 · 763 views
3120. Count the Number of Special Characters I | Leetcode Daily - PythonLeetcode Daily · 6:20 · 416 views
3120. Count the Number of Special Characters I (Leetcode Easy)Programming Live with Larry · 2:57 · 325 views
Count the Number of Special Characters I | LeetCode 3120 | Java Code | Developer CoderDeveloper Coder · 7:28 · 185 views
Count the Number of Special Characters I | LeetCode 3120 - Pythonimpoldev · 3:48 · 124 views
Leetcode 3120 | Count the Number of Special Characters I easy | Python code explanationTechtonic Knights · 4:03 · 119 views
Count the numbers of special characters 1 | leetcode 3120Aman Anand · 9:55 · 114 views
my attempt at solving leetcode 3120: count the number of special characters [SOLVED]Cameron Late · 7:54 · 110 views
3120. Count the Number of Special Characters I Leetcode Weekly Contest 394 | Using Map | EasySucil Dey · 7:47 · 106 views
The problem
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.
Approach overview
Problem Overview: You are given a string containing uppercase and lowercase English letters. A character is considered special if both its lowercase and uppercase versions appear somewhere in the string. The goal is to count how many such characters exist.
Approach 1: Using Sets (O(n) time, O(1) space)
This approach relies on hash-based lookup using two sets. Iterate through the string once and store lowercase characters in one set and uppercase characters in another. After the scan, check each lowercase character and verify whether its uppercase equivalent exists in the uppercase set using constant-time membership checks. The key insight is that sets provide O(1) average lookup, which keeps the solution linear even when checking character pairs. Since the English alphabet is fixed (26 letters), the space usage is effectively constant.
This method is simple to implement and very readable. If you're solving problems involving presence checks or deduplication in a string, a set-based approach is usually the quickest way to reach an optimal solution.
Approach 2: Direct Indexing with Boolean Arrays (O(n) time, O(1) space)
This approach replaces sets with two boolean arrays of size 26. One array tracks whether a lowercase letter a–z appears, and the other tracks whether an uppercase letter A–Z appears. While iterating through the string, convert each character to an index using simple arithmetic (for example, c - 'a' or c - 'A') and mark the corresponding position in the array.
After processing the entire string, iterate from index 0 to 25 and count how many indices are marked in both arrays. Each shared index represents a character whose lowercase and uppercase forms are present. This technique uses direct indexing instead of hashing, which removes hash overhead and guarantees constant-time operations.
This approach is common in problems involving frequency tracking or character presence because arrays are extremely cache-friendly and predictable. It fits naturally when the character domain is small and fixed, such as the English alphabet.
Recommended for interviews: Interviewers generally expect an O(n) solution using either sets or fixed-size arrays. The set-based solution clearly demonstrates understanding of hash lookups, while the boolean array approach shows deeper awareness of constraints and constant-space optimization. Writing the set version first is often fastest during interviews, then mentioning the array optimization shows strong problem-solving depth.
Approach 1: Approach 1: Using Sets
This approach involves using two sets to track lowercase and uppercase appearances of each character. As you iterate over the string, add lowercase characters to one set and uppercase characters to another. After processing the string, check which lowercase characters have their uppercase counterparts present in the sets.
def count_special(word):
lower = set()
upper = set()
for ch in word:
if ch.islower():
lower.add(ch)
elif ch.isupper():
upper.add(ch)
return sum(1 for ch in lower if ch.upper() in upper)
word = "aaAbcBC"
print(count_special(word))import java.util.HashSet;
public class Solution {
public static int countSpecial(String word) {
HashSet<Character> lower = new HashSet<>();
HashSet<Character> upper = new HashSet<>();
for (char ch : word.toCharArray()) {
if (Character.isLowerCase(ch)) {
lower.add(ch);
} else if (Character.isUpperCase(ch)) {
upper.add(ch);
}
}
int specialCount = 0;
for (char ch : lower) {
if (upper.contains(Character.toUpperCase(ch))) {
specialCount++;
}
}
return specialCount;
}
public static void main(String[] args) {
String word = "aaAbcBC";
System.out.println(countSpecial(word));
}
}#include <iostream>
#include <unordered_set>
#include <cctype>
int countSpecial(const std::string &word) {
std::unordered_set<char> lower, upper;
for (char ch : word) {
if (islower(ch)) lower.insert(ch);
if (isupper(ch)) upper.insert(ch);
}
int specialCount = 0;
for (char ch : lower) {
if (upper.find(toupper(ch)) != upper.end()) {
specialCount++;
}
}
return specialCount;
}
int main() {
std::string word = "aaAbcBC";
std::cout << countSpecial(word) << std::endl;
return 0;
}function countSpecial(word) {
const lowerSet = new Set();
const upperSet = new Set();
for (let char of word) {
if (char === char.toLowerCase()) {
lowerSet.add(char);
} else if (char === char.toUpperCase()) {
upperSet.add(char);
}
}
let specialCount = 0;
for (let char of lowerSet) {
if (upperSet.has(char.toUpperCase())) {
specialCount++;
}
}
return specialCount;
}
const word = "aaAbcBC";
console.log(countSpecial(word));#include <stdio.h>
#include <ctype.h>
#include <string.h>
int countSpecial(char* word) {
int lowercasePresent[26] = {0};
int uppercasePresent[26] = {0};
int specialCount = 0;
for(int i = 0; word[i] != '\0'; i++) {
if(islower(word[i])) {
lowercasePresent[word[i] - 'a'] = 1;
} else if(isupper(word[i])) {
uppercasePresent[word[i] - 'A'] = 1;
}
}
for(int i = 0; i < 26; i++) {
if(lowercasePresent[i] && uppercasePresent[i]) {
specialCount++;
}
}
return specialCount;
}
int main() {
char word[] = "aaAbcBC";
printf("%d\n", countSpecial(word));
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int CountSpecial(string word) {
HashSet<char> lowercaseSet = new HashSet<char>();
HashSet<char> uppercaseSet = new HashSet<char>();
foreach (char ch in word) {
if (char.IsLower(ch)) lowercaseSet.Add(ch);
else if (char.IsUpper(ch)) uppercaseSet.Add(ch);
}
int specialCount = 0;
foreach (char ch in lowercaseSet) {
if (uppercaseSet.Contains(char.ToUpper(ch))) {
specialCount++;
}
}
return specialCount;
}
static void Main() {
string word = "aaAbcBC";
Console.WriteLine(CountSpecial(word));
}
}This Python implementation uses sets to dynamically store lowercase and uppercase letters from the input string. It then counts a letter only when it appears in both cases in the input.
Time Complexity: O(n) where n is the length of the string, because we simply iterate over the characters.
Space Complexity: O(1), since the unique letters are limited to 26 lowercase and uppercase English letters.
Approach 2: Approach 2: Direct Indexing with Boolean Arrays
This approach involves using two boolean arrays to directly track all lowercase and uppercase letters. This avoids set operations and provides constant time complexity checking.
def count_special(word):
lower = [False] * 26
upper = [False] * 26
for ch in word:
if ch.islower():
lower[ord(ch) - ord('a')] = True
elif ch.isupper():
upper[ord(ch) - ord('A')] = True
return sum(lower[i] and upper[i] for i in range(26))
word = "aaAbcBC"
print(count_special(word))public class Solution {
public static int countSpecial(String word) {
boolean[] lower = new boolean[26];
boolean[] upper = new boolean[26];
for (char ch : word.toCharArray()) {
if (Character.isLowerCase(ch)) {
lower[ch - 'a'] = true;
} else if (Character.isUpperCase(ch)) {
upper[ch - 'A'] = true;
}
}
int specialCount = 0;
for (int i = 0; i < 26; ++i) {
if (lower[i] && upper[i]) {
specialCount++;
}
}
return specialCount;
}
public static void main(String[] args) {
String word = "aaAbcBC";
System.out.println(countSpecial(word));
}
}#include <iostream>
#include <string>
int countSpecial(const std::string &word) {
bool lower[26] = {false};
bool upper[26] = {false};
for (char ch : word) {
if (islower(ch)) {
lower[ch - 'a'] = true;
} else if (isupper(ch)) {
upper[ch - 'A'] = true;
}
}
int specialCount = 0;
for (int i = 0; i < 26; ++i) {
if (lower[i] && upper[i]) {
specialCount++;
}
}
return specialCount;
}
int main() {
std::string word = "aaAbcBC";
std::cout << countSpecial(word) << std::endl;
return 0;
}function countSpecial(word) {
const lower = new Array(26).fill(false);
const upper = new Array(26).fill(false);
for (let char of word) {
if (char === char.toLowerCase()) {
lower[char.charCodeAt() - 'a'.charCodeAt()] = true;
} else if (char === char.toUpperCase()) {
upper[char.charCodeAt() - 'A'.charCodeAt()] = true;
}
}
let specialCount = 0;
for (let i = 0; i < 26; i++) {
if (lower[i] && upper[i]) {
specialCount++;
}
}
return specialCount;
}
const word = "aaAbcBC";
console.log(countSpecial(word));#include <stdio.h>
#include <ctype.h>
int countSpecial(char* word) {
int lowercase[26] = {0};
int uppercase[26] = {0};
for (int i = 0; word[i] != '\0'; i++) {
if (islower(word[i])) {
lowercase[word[i] - 'a'] = 1;
} else if (isupper(word[i])) {
uppercase[word[i] - 'A'] = 1;
}
}
int specialCount = 0;
for (int i = 0; i < 26; i++) {
if (lowercase[i] && uppercase[i]) {
specialCount++;
}
}
return specialCount;
}
int main() {
char word[] = "aaAbcBC";
printf("%d\n", countSpecial(word));
return 0;
}using System;
class Program {
public static int CountSpecial(string word) {
bool[] lower = new bool[26];
bool[] upper = new bool[26];
foreach (char ch in word) {
if (char.IsLower(ch)) {
lower[ch - 'a'] = true;
} else if (char.IsUpper(ch)) {
upper[ch - 'A'] = true;
}
}
int specialCount = 0;
for (int i = 0; i < 26; i++) {
if (lower[i] && upper[i]) {
specialCount++;
}
}
return specialCount;
}
static void Main() {
string word = "aaAbcBC";
Console.WriteLine(CountSpecial(word));
}
}Python allows direct list operations and indexing, making boolean list a compact form to track character presence in this solution.
Time Complexity: O(n) where n is the size of the string.
Space Complexity: O(1), as boolean lists represent a fixed character set.
Approach 3: Hash Table or Array
We use a hash table or array s to record the characters that appear in the string word. Then we traverse the 26 letters. If both the lowercase and uppercase letters appear in s, the count of special characters is incremented by one.
Finally, return the count of special characters.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Where n is the length of the string word, and |\Sigma| is the size of the character set. In this problem, |\Sigma| leq 128.
function numberOfSpecialChars(word: string): number {
const s: boolean[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => false);
for (let i = 0; i < word.length; ++i) {
s[word.charCodeAt(i)] = true;
}
let ans: number = 0;
for (let i = 0; i < 26; ++i) {
if (s['a'.charCodeAt(0) + i] && s['A'.charCodeAt(0) + i]) {
++ans;
}
}
return ans;
}func numberOfSpecialChars(word string) (ans int) {
s := make([]bool, 'z'+1)
for _, c := range word {
s[c] = true
}
for i := 0; i < 26; i++ {
if s['a'+i] && s['A'+i] {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Sets | Time Complexity: O(n) where n is the length of the string, because we simply iterate over the characters. |
| Approach 2: Direct Indexing with Boolean Arrays | Time Complexity: O(n) where n is the size of the string. |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Sets | O(n) | O(1) | Best general approach when using hash-based membership checks for characters |
| Direct Indexing with Boolean Arrays | O(n) | O(1) | When the character range is fixed (a–z, A–Z) and you want the most lightweight implementation |
Frequently asked questions
Is Count the Number of Special Characters I easy or hard?
Count the Number of Special Characters I is categorized as an Easy problem. The challenge mainly tests basic string traversal and character tracking using sets or arrays. Once you recognize that you only need to check 26 possible letters, the optimal O(n) solution becomes straightforward.
Count the Number of Special Characters I Python/Java solution
In Python or Java, iterate through the string and store lowercase and uppercase characters separately using sets or boolean arrays. After the iteration, compare each lowercase letter with its uppercase equivalent and count matches. The implementation remains O(n) time with constant space.
How to solve Count the Number of Special Characters I in O(n)?
Traverse the string once and track lowercase and uppercase letters separately using sets or boolean arrays. After processing the string, check each character from 'a' to 'z' and count those whose uppercase counterpart also appeared. Constant-time membership checks keep the entire solution linear.
What is the best approach for Count the Number of Special Characters I?
The optimal approach uses a single pass through the string and tracks characters with either sets or fixed-size boolean arrays. Both solutions run in O(n) time and O(1) space because the alphabet size is limited to 26 letters. The boolean array method is slightly more efficient due to direct indexing without hash operations.
Is Count the Number of Special Characters I asked at Google/Amazon/Meta?
Problems involving character tracking and case comparison appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern—using hash sets or arrays to track character presence—is a common interview topic.
What data structure is used in Count the Number of Special Characters I?
The typical data structures are hash sets or fixed-size boolean arrays. Sets provide easy membership checks, while arrays allow direct indexing using character offsets. Both support constant-time lookups, which is necessary to keep the algorithm O(n).
What is the time complexity of Count the Number of Special Characters I?
The time complexity is O(n), where n is the length of the string. You scan the string once to record which characters appear, and then check at most 26 letter pairs. Because the alphabet size is constant, the second step adds only constant overhead.