Jobs

Interviews

Discussions

Count the Number of Special Characters II

Medium

Google

2 views

Topics:

Strings

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 * 10^5
word consists of only lowercase and uppercase English letters.

Count the Number of Special Characters II

Medium

Google

2 views

Topics:

Strings

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 * 10^5
word consists of only lowercase and uppercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are considered 'special' beyond the standard alphanumeric characters (a-z, A-Z, 0-9)? Should I consider whitespace, punctuation, or Unicode characters as special?
What is the expected input data type? Is it a string, an array of characters, or something else?
Are there any limitations on the length of the input string or array? Should I be concerned about potential integer overflow when counting?
How should I handle null or empty input? Should I return 0, throw an exception, or is there another specified behavior?
Is the character case-sensitive when determining if a character is alphanumeric? For example, should 'a' and 'A' both be considered alphanumeric?

Brute Force Solution

Approach

We want to find how many special characters are in a given piece of text. The brute force way means we will look at each character one by one and determine if it is a special character. We then count up all the special characters we identified.

Here's how the algorithm would work step-by-step:

Start by picking the very first character of the text.
Check if that character is a special character. If it is, add one to our special character count.
Now, move on to the next character in the text.
Again, check if this character is a special character. If it is, add one to our special character count.
Keep doing this for every single character in the text, one after the other.
After you've checked every character, the final count you have is the total number of special characters.

Code Implementation

def count_special_characters_brute_force(text):
    special_character_count = 0
    for character in text:
        #Check if the current char is special
        if not character.isalnum():

            special_character_count += 1

        #Increase counter if special

    return special_character_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input text character by character. For each of the n characters in the text, it performs a constant-time check to determine if it's a special character. Therefore, the number of operations is directly proportional to the length of the text, resulting in a linear time complexity. The total operations approximate n, hence the Big O notation is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the text character by character, using a counter to keep track of special characters. It does not create any auxiliary data structures like arrays, hash maps, or lists to store intermediate results. The only extra memory used is for the counter variable, which remains constant regardless of the size of the input text (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To quickly count special characters, we'll avoid checking each possible character separately. Instead, we'll pre-process the allowed characters for fast lookups, then go through the input string once to efficiently count the special characters. This avoids redundant checks and speeds up the process considerably.

Here's how the algorithm would work step-by-step:

First, create a set of all the allowed characters. Think of it like creating a club membership list.
Next, go through each character in the input string one by one.
For each character, quickly check if it is a member of the 'allowed character' club we created earlier. If it is NOT in the 'allowed character' club, it is considered a special character.
Keep a running total of how many special characters you find.
Once you've checked every character in the input string, report the final total of special characters.

Code Implementation

def count_the_number_of_special_characters(input_string):
    allowed_characters = set("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ")

    # Initialize counter for special chars
    special_character_count = 0

    for char in input_string:
        #Check if the character is NOT in the allowed set
        if char not in allowed_characters:

            special_character_count += 1

    # Returns the total count of the special characters
    return special_character_count

Big(O) Analysis

Time Complexity

O(n) – Creating the set of allowed characters takes O(m) time, where m is the number of allowed characters. Iterating through the input string of length n takes O(n) time. Inside the loop, checking if a character exists in the set takes O(1) time on average. Therefore, the overall time complexity is dominated by the iteration through the input string, resulting in O(n + m), which simplifies to O(n) assuming 'm' is a constant or significantly smaller than 'n'.

Space Complexity

O(M) – The algorithm creates a set of allowed characters. The size of this set depends on the number of unique allowed characters, which we denote as M. The set stores these M allowed characters, taking up space proportional to M. No other significant auxiliary data structures are created. Therefore, the space complexity is O(M), where M is the number of allowed characters.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 if the input string is null or empty, as there are no characters to check.
String containing only whitespace characters	Iterate through the string and check each character if it's not whitespace to determine the special character count.
String with maximum allowed length	Ensure the solution's time and space complexity scale efficiently to avoid timeouts or memory errors with large strings.
String containing a large number of special characters	The solution should accurately count all special characters without integer overflow issues in the counter.
Special characters at the beginning or end of the string	The iteration should handle special characters located at the string's boundaries correctly.
String with Unicode characters	The solution should properly identify and count special characters in Unicode strings, considering different character encodings.
String containing characters outside the typical ASCII range that are still considered special	Define the range of acceptable characters precisely and correctly identify special ones outside of the standard range
String containing a mix of ASCII and non-ASCII characters	Ensure consistent handling of both ASCII and non-ASCII characters when identifying special characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are considered 'special' beyond the standard alphanumeric characters (a-z, A-Z, 0-9)? Should I consider whitespace, punctuation, or Unicode characters as special?
What is the expected input data type? Is it a string, an array of characters, or something else?
Are there any limitations on the length of the input string or array? Should I be concerned about potential integer overflow when counting?
How should I handle null or empty input? Should I return 0, throw an exception, or is there another specified behavior?
Is the character case-sensitive when determining if a character is alphanumeric? For example, should 'a' and 'A' both be considered alphanumeric?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by picking the very first character of the text.
Check if that character is a special character. If it is, add one to our special character count.
Now, move on to the next character in the text.
Again, check if this character is a special character. If it is, add one to our special character count.
Keep doing this for every single character in the text, one after the other.
After you've checked every character, the final count you have is the total number of special characters.

Code Implementation

def count_special_characters_brute_force(text):
    special_character_count = 0
    for character in text:
        #Check if the current char is special
        if not character.isalnum():

            special_character_count += 1

        #Increase counter if special

    return special_character_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a set of all the allowed characters. Think of it like creating a club membership list.
Next, go through each character in the input string one by one.
For each character, quickly check if it is a member of the 'allowed character' club we created earlier. If it is NOT in the 'allowed character' club, it is considered a special character.
Keep a running total of how many special characters you find.
Once you've checked every character in the input string, report the final total of special characters.

Code Implementation

def count_the_number_of_special_characters(input_string):
    allowed_characters = set("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ")

    # Initialize counter for special chars
    special_character_count = 0

    for char in input_string:
        #Check if the character is NOT in the allowed set
        if char not in allowed_characters:

            special_character_count += 1

    # Returns the total count of the special characters
    return special_character_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 if the input string is null or empty, as there are no characters to check.
String containing only whitespace characters	Iterate through the string and check each character if it's not whitespace to determine the special character count.
String with maximum allowed length	Ensure the solution's time and space complexity scale efficiently to avoid timeouts or memory errors with large strings.
String containing a large number of special characters	The solution should accurately count all special characters without integer overflow issues in the counter.
Special characters at the beginning or end of the string	The iteration should handle special characters located at the string's boundaries correctly.
String with Unicode characters	The solution should properly identify and count special characters in Unicode strings, considering different character encodings.
String containing characters outside the typical ASCII range that are still considered special	Define the range of acceptable characters precisely and correctly identify special ones outside of the standard range
String containing a mix of ASCII and non-ASCII characters	Ensure consistent handling of both ASCII and non-ASCII characters when identifying special characters.