Skip to main content

Hashing

Count the Number of Special Characters II Solution In C++/Java/Python/Javascript

Problem Description

You are given a string word. A letter is considered "special" if:
It appears in both lowercase (e.g., 'a') and uppercase (e.g., 'A') forms in the string.
All the lowercase versions of the letter come before the first uppercase version in the string.
Your task is to count how many such "special" letters exist in the string and return that count.
count-the-number-of-special-characters-ii - Question Description

Examples:
Input: word = “aaAbcBC”
Output: 3
Explanation: The special characters are ‘a’,’b’,’c’.

Input: word = “abc”
Output: 0
Explanation: There are no special characters in the string.

Constraints:

1<= word.length <=2*10⁵
Word consists of only lowercase and uppercase English letters.

Brute-force Approach:

Okay, so here's the thought process:

What comes to mind after reading the problem statement?

We need to make up the string where each lowercase letter appears before its corresponding uppercase letter appears in string word.

If a character from a word satisfies this condition, we add it to the answer. After processing all characters in word, we return the answer.

💡
Try it Yourself!

How to do it:

  • Iterate through the string: We traverse the given string character by character.
  • Identify Lowercase Letters: We focus only on lowercase letters as they are the potential candidates for being "special."
  • Check for Uppercase Occurrence: For each lowercase letter, we check if its corresponding uppercase letter exists within the string.
  • Validate Order: If the uppercase letter exists, we ensure that all occurrences of the lowercase letter appear before the first occurrence of the uppercase letter.
  • Count Special Letters: If all conditions are met (lowercase letter exists, uppercase letter exists, and the order of occurrences is correct), we increment the count of special letters.
count-the-number-of-special-characters-ii - Brute Force

Let's walk through an example: 

Dry run for Input: word = “aaAbcBC”

Step 1: At i = 0, word[i] = 'a'

  1. Identify Lowercase: 'a' is a lowercase letter.
  2. Check for Uppercase: Its corresponding uppercase letter 'A' exists in the string at i = 2.
  3. Validate Order: All occurrences of 'a' (at i = 0 and i = 1) appear before the first occurrence of 'A' (at i = 2).
  4. Count Special Letter: Increment count to 1.

Step 2: At i = 1, word[i] = 'a'

  1. Identify Lowercase: 'a' is already processed.
  2. Skip further checks for this occurrence.
  3. Move to the next character.

Step 3: At i = 2, word[i] = 'A'

  1. Identify Uppercase: Skip this character since it is not lowercase.
  2. Move to the next character.

Step 4: At i = 3, word[i] = 'b'

  1. Identify Lowercase: 'b' is a lowercase letter.
  2. Check for Uppercase: Its corresponding uppercase letter 'B' exists in the string at i = 5.
  3. Validate Order: All occurrences of 'b' (at i = 3) appear before the first occurrence of 'B' (at i = 5).
  4. Count Special Letter: Increment count to 2.

Step 5: At i = 4, word[i] = 'c'

  1. Identify Lowercase: 'c' is a lowercase letter.
  2. Check for Uppercase: Its corresponding uppercase letter 'C' exists in the string at i = 6.
  3. Validate Order: All occurrences of 'c' (at i = 4) appear before the first occurrence of 'C' (at i = 6).
  4. Count Special Letter: Increment count to 3.

Step 6: At i = 5, word[i] = 'B'

  1. Identify Uppercase: Skip this character since it is not lowercase.
  2. Move to the next character.

Step 7: At i = 6, word[i] = 'C'

  1. Identify Uppercase: Skip this character since it is not lowercase.
  2. Move to the next character.

Output: 3

How to code it up:

1.Initialize Count:

  • Start by initializing a variable special count to store the count of special letters.

 2.Outer Loop:

  • Iterate through each character in the string using a loop.
  • Check if the current character is a lowercase letter.
  • If it is, assign the current lowercase letter to lower and its uppercase counterpart to upper.

3. Inner Loop:

  • Iterate through the string again using a for loop to validate the following:
    • If the uppercase counterpart appears before the lowercase character's position, set isSpecial = false and exit the loop.
    • If another lowercase occurrence of the character appears after its uppercase counterpart, set isSpecial = false and exit the loop.
  • These checks ensure that the order constraint is met: no lowercase letter can follow its uppercase counterpart.

4.Check Uppercase Existence:

  • Check if the corresponding uppercase character exists in the string.

5.Increment Count:

  • If both conditions (order and existence) are satisfied, increment the count.

Code Implementation
1. C++ Try on Compiler 
class Solution {
    public:
    int numberOfSpecialChars(string word) {
        int specialCount = 0;


    // Outer loop: Iterate through the string
    for (int i = 0; i < word.size(); ++i) {
    // Check if the character is lowercase
        if (islower(word[i])) {  
            char lower = word[i];
            char upper = toupper(lower);
         // Assume the letter is special
            bool isSpecial = true;  


            // Inner loop: Check for uppercase counterpart
            for (int j = 0; j < word.size(); ++j) {
                if (word[j] == upper) {
        // Uppercase appears before lowercase
                    if (j < i) {  
                        isSpecial = false;
                        break;
                    }
                }
             // If  lowercase appears after its uppercase counterpart
                if (word[j] == lower && j > i) {
                    isSpecial = false;
                    break;
                }
            }


            // If the letter is special, increment the count
            if (isSpecial && word.find(upper) != string::npos) {
                ++specialCount;
            }
        }
    }


    return specialCount;
    }
};

2. Java Try on Compiler 
class Solution {
    public int numberOfSpecialChars(String word) {
        int specialCount = 0;


        // Outer loop: Iterate through the string
    for (int i = 0; i < word.length(); i++) {
        // Check if the character is lowercase
        if (Character.isLowerCase(word.charAt(i))) {
        char lower = word.charAt(i);
        char upper = Character.toUpperCase(lower);
    boolean isSpecial = true; // Assume the letter is special


     // Inner loop: Check for uppercase counterpart
        for (int j = 0; j < word.length(); j++) {
         if (word.charAt(j) == upper) {
      // Uppercase appears before lowercase
        if (j < i) {
            isSpecial = false;
            break;
                        }
                    }
          //  If lowercase appears after its uppercase counterpart
        if (word.charAt(j) == lower && j > i) {
             isSpecial = false;
             break;
                    }
                }


     // If the letter is special, increment the count
    if (isSpecial && word.contains(String.valueOf(upper))) {
     specialCount++;
                }
            }
        }


        return specialCount;
    }
}

3. Python Try on Compiler 
class Solution(object):
    def numberOfSpecialChars(self, word):
        special_count = 0


        # Outer loop: Iterate through the string
        for i in range(len(word)):
            # Check if the character is lowercase
            if word[i].islower():
                lower = word[i]
                upper = lower.upper()
                # Assume the letter is special
                is_special = True


                # Inner loop: Check for uppercase counterpart
                for j in range(len(word)):
                    if word[j] == upper:
                        # Uppercase appears before lowercase
                        if j < i:
                            is_special = False
                            break
                    # If lowercase appears after its uppercase counterpart
                    if word[j] == lower and j > i:
                        is_special = False
                        break


                # If the letter is special, increment the count
                if is_special and upper in word:
                    special_count += 1


        return special_count

4. Javascript Try on Compiler 
/**
 * @param {string} word
 * @return {number}
 */
   var numberOfSpecialChars = function(word) {
      let specialCount = 0;


        // Outer loop: Iterate through the string
        for (let i = 0; i < word.length; i++) {
            // Check if the character is lowercase
  if (word[i] === word[i].toLowerCase() && word[i] !==   word[i].toUpperCase()) {
                let lower = word[i];
                let upper = lower.toUpperCase();
                let isSpecial = true; // Assume the letter is special


                // Inner loop: Check for uppercase counterpart
                for (let j = 0; j < word.length; j++) {
                    if (word[j] === upper) {
                        // Uppercase appears before lowercase
                        if (j < i) {
                            isSpecial = false;
                            break;
                        }
                    }
                   // If lowercase appears after its uppercase counterpart
                    if (word[j] === lower && j > i) {
                        isSpecial = false;
                        break;
                    }
                }


                // If the letter is special, increment the count
                if (isSpecial && word.includes(upper)) {
                    specialCount++;
                }
            }
        }
 return specialCount; 
};

Time Complexity: O(n²)

Let's walk through the time complexity:
Step1: Outer Loop:

  • The outer loop iterates through each character in the string word (length n).
  • This loop runs n times, as it processes every character from index 0 to n-1.

Step2: Inner Loop:

  • For each character processed in the outer loop, the inner loop iterates through the entire string again to check the conditions for being a "special" character.
  • This inner loop also runs n times for each iteration of the outer loop.

Combining the Two Loops:

  • For each iteration of the outer loop, the inner loop runs n times.
  • Thus, the total number of operations can be expressed as:
    • n+n+n+… (repeated n times).
  • This results in O(n)×O(n)=O(n²)

Where:

n is the length of the String Word.

Space Complexity: O(n)

Auxiliary Space Complexity: O(1)
Explanation: The algorithm uses a constant amount of extra space for temporary variables like lower, upper, isSpecial, and counters like specialCount. 

Total Space Complexity: O(n)
Explanation: The input string word itself occupies O(n) space, where n is the length of the string.

So, the total space complexity will be O(n).

Will the Brute Force Approach Work Within the Given Constraints?

Let’s analyze the problem with respect to the given constraints:

For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the length of the string word is at most 10⁵, the solution might not execute within the given time limits. 

Since O(n²) results in a maximum of 10¹⁰ operations (for n =10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.

When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations.

Thus, while the solution meets the time limits for a single test case O(n²) time complexity poses a risk for Time Limit Exceeded (TLE).

Can we optimize it?

In our previous brute-force approach, we repeatedly looked for the position of uppercase characters for each lowercase character in word. While this method is straightforward, it results in O(n²)  time complexity due to the repeated comparisons.

Where are we lagging?

The inefficiency comes from the fact that for each lowercase character in the string, we are iterating over the string word to check if its corresponding uppercase character exists and appear later in the string .This results in an O(n²) complexity.

But how can we do this in an optimized way?

What if we can store the last occurrence of each lowercase character as we traverse the string .This avoids redundant lookups for the same lowercase characters.

Now, instead of checking all occurrences of lowercase characters and then checking uppercase characters, we can store lowercase characters occurrences as values  in a hashmap (or dictionary) to make it easy and fast to look up.

Here’s how we do it:

We first iterate through the string word to build a hash map where each lowercase character is mapped to its last occurrence index. This ensures we capture the position of the latest appearance of each lowercase letter. 

Next, we process each entry in the hash map to determine its uppercase counterpart. we check if the uppercase version of the character exists in the string and whether its position occurs after the stored lowercase index. 

If this condition is satisfied, we increment the count of special characters. 

Finally, we return the total count of such special characters as the result.

0:00
/1:28

count-the-number-of-special-characters-ii - Optimal Animation

Let’s take an example to make this clearer.

Example:
Input: word=”aaAbcBC”
Step 1: Map Lowercase Characters

  • Initialize map to store occurrences off lowercase char.
  • Traverse the string word and store the last position of lowercase letters:
    • Index 0: 'a' → map = {'a': 0}
    • Index 1: 'a' → map = {'a': 1} (updated position)
    • Index 2: 'A' → Not a lowercase letter, skip.
    • Index 3: 'b' → map = {'a': 1, 'b': 3}
    • Index 4: 'c' → map = {'a': 1, 'b': 3, 'c': 4}
    • Index 5: 'B' → Not a lowercase letter, skip.
    • Index 6: 'C' → Not a lowercase letter, skip.

Final map: {'a': 1, 'b': 3, 'c': 4}

Step 2: Count Special Characters

  • Initialize count = 0.
  • Iterate over each entry in map:
    1. Key = 'a', Lowercase Position = 1
      • Uppercase counterpart: 'A'.
      • Position of 'A': 2 (found using word.find('A')).
      • Check: 2 > 1 → True. Increment count = 1.
    3. Key = 'b', Lowercase Position = 3
      • Uppercase counterpart: 'B'.
      • Position of 'B': 5.
      • Check: 5 > 3 → True. Increment count = 2.
    5. Key = 'c', Lowercase Position = 4
      • Uppercase counterpart: 'C'.
      • Position of 'C': 6.
      • Check: 6 > 4 → True. Increment count = 3.

Step 3: Return the Count

  • The total count of special characters is 3.

Output: 3

How to code it up?

1. Building the Hashmap:
Traverse the string word and store the last seen position of every lowercase character in a hashmap.

2. Processing the Hashmap:
For each lowercase character in the hashmap.
Compute its uppercase character and check if the uppercase exists and is positioned after the lowercase character.

3. Counting Valid Characters:
Increment the count if the condition is satisfied.

Code Implementation
1. C++ Try on Compiler 
class Solution {
public:
    int numberOfSpecialChars(const std::string& word) {
   // Store last positions of lowercase characters
    unordered_map<char, int> map;
       
        // First pass: Build the hashmap
        for (int i = 0; i < word.size(); ++i) {
            if (islower(word[i])) {
                map[word[i]] = i;
            }
        }
    //To count valid characters
        int count = 0;
        // Second pass: Process the hashmap
        for (const auto& entry : map) {
    //  // Lowercase character
            char lower = entry.first;          
           // // Position of lowercase character
            int lowerPos = entry.second;      
             // Uppercase counterpart
              char upper = toupper(lower);  


 // Check if uppercase exists and appears after the lowercase character
            int upperPos = word.find(upper);
            if (upperPos > lowerPos) {
                count++;
            }
        }
 // Return the total count of valid characters
        return count;
    }
};

2. Java Try on Compiler 
class Solution {
    public int numberOfSpecialChars(String word) {
        // First pass: Build the hashmap
        Map<Character, Integer> map = new HashMap<>();
    // Store last positions of lowercase characters
        for (int i = 0; i < word.length(); i++) {
            if (Character.isLowerCase(word.charAt(i))) {
                map.put(word.charAt(i), i);
            }
        }


        // To count valid characters
        int count = 0;


        // Second pass: Process the hashmap
        for (char lower : map.keySet()) {
            // Position of lowercase character
            int lowerPos = map.get(lower);
            // Uppercase counterpart
            char upper = Character.toUpperCase(lower);


    // Check if uppercase character exists and appears after the lowercase character
            int upperPos = word.indexOf(upper);
            if (upperPos > lowerPos) {
                count++;
            }
        }


        // Return the total count of valid characters
        return count;
    }
}

3. Python Try on Compiler 
class Solution(object):
    def numberOfSpecialChars(self, word):
        # Step 1: Store the last positions of lowercase characters in a dictionary
        char_map = {}
        for i, char in enumerate(word):
             # Check if the character is lowercase
           if char.islower(): 
                char_map[char] = i  
       
      # Step 2: Count valid special characters
        count = 0


        for lower, lower_pos in char_map.items():
            # Find the uppercase counterpart
            upper = lower.upper()
            # Find the position of the uppercase character
            upper_pos = word.find(upper)


            # Check if uppercase exists and appears after the lowercase character
            if upper_pos > lower_pos:
                count += 1


        return count

4. Javascript Try on Compiler 
/**
 * @param {string} word
 * @return {number}
 */
var numberOfSpecialChars = function(word) {
     // First pass: Build the hashmap
        const map = new Map();


     // Store last positions of lowercase characters
        for (let i = 0; i < word.length; i++) {
            if (word[i] === word[i].toLowerCase()) {
                map.set(word[i], i);
            }
        }


        // To count valid characters
        let count = 0;


        // Second pass: Process the hashmap
        for (const [lower, lowerPos] of map) {
            // Uppercase counterpart
            const upper = lower.toUpperCase();


            // Check if uppercase exists and appears after the lowercase character
            const upperPos = word.indexOf(upper);
            if (upperPos > lowerPos) {
                count++;
            }
        }


        // Return the total count of valid characters
        return count;
};

Time Complexity: O(n)

1.Building the Hash Map

  • We iterate through the string word once to find the positions of all lowercase letters.
  • For each lowercase letter:
    • We store its last position in the hashmap.
    • This operation is O(1) on average for insertion into the map.
  • Total time for this step: O(n) where n is the length of word.

2.Processing the Hash Map

  • We iterate over all entries in the map. The size of the map is at most 26 (since there are only 26 lowercase letters in the English alphabet).
  • For each entry:
    1. Retrieve the uppercase counterpart using toupper(lower) (O(1)).
    2. check if the position of uppercase characters appears after the last recorded position of the corresponding lowercase letter.
    3. This performs a linear scan of the string from the beginning and takes O(n) in the worst case.
  • Total time for this step: O(26×n)=O(n) as the number of lowercase letters (26) is constant.

3. Combining both steps:

  •  Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

Auxiliary Space complexity: O(1)
Explanation: we used the map to store at most 26 key-value pairs (one for each lowercase letter).Each key-value pair requires O(1)space.

Total Space Complexity: O(n).
Explanation: We are given string word. Let the length of string is n.
So, the total space complexity will be O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

1. Can Convert String in K Moves

You are given two strings s and t, and a number k. Your task is to determine if you can transform string s into string t in k moves or fewer.

How the transformation works:

  1. In each move, you can choose a character from s that hasn’t been changed in a previous move.
  2. You can "shift" the selected character forward in the alphabet. Shifting means replacing the character with the next one (with 'z' wrapping around to 'a').
    • For example:
      • Shifting 'a' by 1 becomes 'b'.
      • Shifting 'z' by 1 becomes 'a'.
  4. In the ith move, the character you select can be shifted exactly i times.

You need to check if it's possible to transform s into t in no more than k moves. Return true if it is possible, otherwise return false.

2.Vowel Spellchecker

You need to build a spell checker that corrects spelling mistakes based on given rules. The task is to find a correct word from the provided wordlist for each query word and return it.

The spell checker handles two types of mistakes:

1. Capitalization Mistakes:

If the query word matches a word in the wordlist regardless of uppercase or lowercase differences, return the word from the wordlist with the correct capitalization.

  • Example:
    • wordlist = ["yellow"], query = "YellOw" → Correct word: "yellow"
    • wordlist = ["Yellow"], query = "yellow" → Correct word: "Yellow"
    • wordlist = ["yellow"], query = "yellow" → Correct word: "yellow"

2. Vowel Mistakes:

If the query matches a word in the wordlist after replacing vowels ('a', 'e', 'i', 'o', 'u') with any other vowel, return the word with the correct case from the wordlist.

  • Example:
    • wordlist = ["YellOw"], query = "yollow" → Correct word: "YellOw"
    • wordlist = ["YellOw"], query = "yeellow" → No match → Return ""
    • wordlist = ["YellOw"], query = "yllw" → No match → Return ""

Precedence Rules:

When checking queries, apply the following rules in this order:

  1. Exact match: Return the same word if the query matches the word exactly (case-sensitive).
  2. Case-insensitive match: Return the first word that matches when ignoring capitalization differences.
  3. Vowel error match: Return the first word that matches by ignoring vowel differences.
  4. No match: Return an empty string if no rule applies