3120. Count the Number of Special Characters I

EasyHash TableString

Problem Description

You are given a string word. A letter is considered special if it appears in both lowercase and uppercase forms within the word. The goal is to determine the count of such special letters in the given string.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we can utilize a set data structure to store and quickly check the presence of characters in the given string. The primary idea is to iterate over all the lowercase and uppercase alphabetic characters and check whether both versions of each character exist in the set. If both versions exist, it indicates that the letter is special. By doing this for each letter from 'a' to 'z', we count the number of special characters and return this count. This approach leverages the efficiency of set lookups to achieve the solution in a straightforward and effective manner.

Solution Approach

The solution utilizes a set to efficiently check the presence of both lowercase and uppercase forms of each letter. Here's a step-by-step breakdown of the approach:

Use a Set for Character Storage:
We begin by converting the string word into a set s. This allows us to benefit from constant time complexity for checking if a character exists in word.
```
s = set(word)
```
Iterate Over Alphabet Pairs:
We iterate over pairs of lowercase and uppercase alphabets using zip(ascii_lowercase, ascii_uppercase). This will give us pairs like ('a', 'A'), ('b', 'B'), and so on.

Check for Special Characters:
For each pair of letters (a, b), we check whether both a and b are present in set s. If they are, it means the letter is "special" as it appears in both forms in word.

sum(a in s and b in s for a, b in zip(ascii_lowercase, ascii_uppercase))

Count and Return:
We sum up the results of the above checks to get the total count of special characters, which is then returned as the output of the function.

By using a set to store characters and checking for the existence of both uppercase and lowercase forms, the solution efficiently determines the count of special letters with a time complexity of O(n + 26), where n is the length of the string, and 26 operations correspond to checking all alphabetical pairs.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to see how this solution works in practice. Suppose we're given the string word = "AaBbCcXxYyZz". We need to find out how many special letters are present in this string.

Create a Set from the String:

Convert the string word into a set s to store all unique characters from the string. In this example, s will look like this:

s = {'A', 'a', 'B', 'b', 'C', 'c', 'X', 'x', 'Y', 'y', 'Z', 'z'}

Iterate Over Alphabet Pairs:

Next, iterate over the pairs of lowercase and uppercase letters: ('a', 'A'), ('b', 'B'), ('c', 'C'), ..., ('z', 'Z').
Check for Special Characters:

For each pair (a, b), check if both characters a and b are in the set s. Let's walk through a few pairs:
- For the pair ('a', 'A'), both 'a' and 'A' are in s, so 'a' is a special letter.
- For ('b', 'B'), both 'b' and 'B' are in s, so it's also special.
- For ('c', 'C'), both are present; hence, 'c' is special.
- This pattern continues for the other pairs ('x', 'X'), ('y', 'Y'), and ('z', 'Z').
The set s does not include both cases for letters not present in word, so they aren't counted.
Count and Return:

Summing the results from these checks gives us the total count of special letters in word. In this example:
- Special letters found: 'a', 'b', 'c', 'x', 'y', 'z'.
- Total count = 6

Thus, the function would return 6 as the output for this string, which represents the number of special letters.

Solution Implementation

1from string import ascii_lowercase, ascii_uppercase
2
3class Solution:
4    def numberOfSpecialChars(self, word: str) -> int:
5        # Convert the input string 'word' into a set to identify unique characters
6        unique_chars = set(word)
7      
8        # Calculate the number of characters that have both lower and uppercase representations
9        # present in the set of unique characters
10        return sum(lower in unique_chars and upper in unique_chars 
11                   for lower, upper in zip(ascii_lowercase, ascii_uppercase))
12

1class Solution {
2    public int numberOfSpecialChars(String word) {
3        // Boolean array to track the presence of characters within the alphabet range
4        boolean[] isPresent = new boolean['z' + 1];
5      
6        // Iterate over the characters in the given word
7        for (int i = 0; i < word.length(); ++i) {
8            // Mark the character as present
9            isPresent[word.charAt(i)] = true;
10        }
11      
12        int count = 0; // Initialize a counter for special characters
13      
14        // Loop through the alphabet range (0 to 25 for 'a' to 'z')
15        for (int i = 0; i < 26; ++i) {
16            // Check if both lowercase and uppercase forms are present
17            // For example, check both 'a' and 'A', 'b' and 'B', etc.
18            if (isPresent['a' + i] && isPresent['A' + i]) {
19                ++count; // Increment the counter if both forms are present
20            }
21        }
22      
23        return count; // Return the count of special characters
24    }
25}
26

1#include <string>
2#include <vector>
3
4class Solution {
5public:
6    // This method counts the number of special characters in the given string.
7    int numberOfSpecialChars(std::string word) {
8        // Create a vector to keep track of the characters present in the string.
9        std::vector<bool> isPresent('z' + 1, false);
10
11        // Mark each character present in the string.
12        for (char& c : word) {
13            isPresent[c] = true;
14        }
15
16        int specialCount = 0;
17      
18        // Check each letter of the alphabet for both lower and uppercase presence.
19        for (int i = 0; i < 26; ++i) {
20            // Increment the count if both the lower and uppercase versions of the letter are present.
21            specialCount += isPresent['a' + i] && isPresent['A' + i];
22        }
23
24        return specialCount;
25    }
26};
27

1/**
2 * Counts the number of special characters in a given word.
3 * A special character is defined as a letter that appears in both
4 * uppercase and lowercase in the word.
5 * 
6 * @param word - The input string to be analyzed.
7 * @returns The number of special characters.
8 */
9function numberOfSpecialChars(word: string): number {
10    // Create an array to keep track of which characters appear in the word.
11    const charPresence: boolean[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => false);
12  
13    // Mark the presence of each character in the input word.
14    for (let i = 0; i < word.length; ++i) {
15        charPresence[word.charCodeAt(i)] = true;
16    }
17  
18    let count: number = 0; // Variable to count the number of special characters.
19  
20    // Iterate over the alphabet (26 letters).
21    for (let i = 0; i < 26; ++i) {
22        // Check if both the lowercase and uppercase forms of a letter appear in the word.
23        if (charPresence['a'.charCodeAt(0) + i] && charPresence['A'.charCodeAt(0) + i]) {
24            ++count; // Increment count if both cases appear.
25        }
26    }
27  
28    return count; // Return the total number of special characters found.
29}
30

Time and Space Complexity

The time complexity of the code is O(n + |\Sigma|), where n is the length of the string word, and |\Sigma| is the size of the character set. This accounts for creating the set of characters from word and then iterating over the fixed character set (comprising both lowercase and uppercase alphabets).

The space complexity is O(|\Sigma|), where |\Sigma| refers to the number of unique characters in the input set. In this problem, since |\Sigma| is a constant (at most 128, to include all lowercase and uppercase letters), the space complexity is effectively constant, denoted typically as O(1).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know