Facebook Pixel

3121. Count the Number of Special Characters II

MediumHash TableString
Leetcode Link

Problem Description

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.

Intuition

To determine the number of special letters, we need to keep track of where each lowercase and uppercase letter first appears in the string. The goal is to ensure that every lowercase occurrence of a letter appears before its uppercase counterpart. This involves:

  1. Identifying the Position: Use dictionaries to record the first and last occurrence of each letter. This helps figure out the sequence in which they appear.

  2. Validation: After recording the occurrences, compare the positions of the lowercase and uppercase versions of each letter. A letter is deemed special if the last position of a lowercase letter is less than the first position of its uppercase counterpart.

This approach efficiently determines special characters by leveraging the order of letter appearances, allowing us to count how many such instances exist.

Solution Approach

Solution 1: Hash Table or Array

The approach uses two hash tables, first and last, to track the first and last occurrences of each character in the string word. Here's how it works:

  1. Initialization: Create two dictionaries, first and last, to store indices of characters.

  2. Iteration through the String:

    • Traverse the string word character by character.
    • For each character c, if it's the first time c appears, record its index in the first dictionary.
    • Regardless of whether it's the first appearance, update the last dictionary to store the current index as the last occurrence.

  3. Determining Special Characters:

    • Iterate over each pair of corresponding lowercase and uppercase letters (from a to z and A to Z).
    • For each pair (a, b), check if:
      • Both a exists in last and b exists in first.
      • The last occurrence of a is before the first occurrence of b (last[a] < first[b]).
    • If both conditions are true, increment the count of special letters.

This approach efficiently uses space to store first and last positions, and leverages these positions to determine the special status of characters.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a simple example using the solution approach described. Consider the string word = "aAbBcCz". We want to determine the number of special letters in this string.

  1. Initialization:

    • Create two dictionaries, first and last.

  2. Iteration through the String:

    • Traverse the string character by character.

    • For character 'a' at index 0, it's the first occurrence, so first['a'] = 0. Also, last['a'] = 0 (since it's currently the last occurrence).

    • For character 'A' at index 1, it's the first occurrence, so first['A'] = 1. Also, last['A'] = 1 (since it's currently the last occurrence).

    • For character 'b' at index 2, it's the first occurrence, so first['b'] = 2. Also, last['b'] = 2.

    • For character 'B' at index 3, it's the first occurrence, so first['B'] = 3. Also, last['B'] = 3.

    • For character 'c' at index 4, it's the first occurrence, so first['c'] = 4. Also, last['c'] = 4.

    • For character 'C' at index 5, it's the first occurrence, so first['C'] = 5. Also, last['C'] = 5.

    • For character 'z' at index 6, it's the first occurrence, so first['z'] = 6. Also, last['z'] = 6.

  3. Determining Special Characters:

    • Iterate from a to z and compare with A to Z.

    • For ('a', 'A'):

      • last['a'] = 0 and first['A'] = 1. Since 0 < 1, 'a' is special.

    • For ('b', 'B'):

      • last['b'] = 2 and first['B'] = 3. Since 2 < 3, 'b' is special.

    • For ('c', 'C'):

      • last['c'] = 4 and first['C'] = 5. Since 4 < 5, 'c' is special.

    • For any other combinations such as ('z', 'Z'):

      • There's no uppercase Z to Check, so 'z' is not special.

    The result is that there are 3 special letters: 'a', 'b', and 'c'.

Solution Implementation

1from string import ascii_lowercase, ascii_uppercase
2
3class Solution:
4    def numberOfSpecialChars(self, word: str) -> int:
5        # dictionaries to store the first and last index of each character
6        first = {}
7        last = {}
8      
9        # iterate over the word with both index and character
10        for index, char in enumerate(word):
11            # record the first occurrence of the character
12            if char not in first:
13                first[char] = index
14            # record the last occurrence of the character
15            last[char] = index
16      
17        # calculate the number of special character pairs
18        return sum(
19            # check if both characters exist and if the last occurrence of the first is before the first occurrence of the second
20            a in last and b in first and last[a] < first[b]
21            # loop over pairs of lowercase and uppercase letters
22            for a, b in zip(ascii_lowercase, ascii_uppercase)
23        )
24
1class Solution {
2    public int numberOfSpecialChars(String word) {
3        // Arrays to store the first and last occurrence of each character
4        int[] firstOccurrence = new int['z' + 1];
5        int[] lastOccurrence = new int['z' + 1];
6      
7        // Iterating over each character in the input string
8        for (int i = 1; i <= word.length(); ++i) {
9            char currentChar = word.charAt(i - 1);
10            int index = currentChar;
11          
12            // Record the first occurrence of the character if not recorded yet
13            if (firstOccurrence[index] == 0) {
14                firstOccurrence[index] = i;
15            }
16            // Always update the last occurrence of the character
17            lastOccurrence[index] = i;
18        }
19      
20        int specialCount = 0;
21      
22        // Check for special characters a to z
23        for (char c = 'a'; c <= 'z'; ++c) {
24            int lowerIndex = c;
25            int upperIndex = c - 'a' + 'A'; // Corresponding uppercase character
26          
27            // Check if the lowercase character and uppercase character have valid occurrences
28            // and if the last occurrence of lowercase is before the first of uppercase
29            if (lastOccurrence[lowerIndex] > 0 && firstOccurrence[upperIndex] > 0 
30                && lastOccurrence[lowerIndex] < firstOccurrence[upperIndex]) {
31                ++specialCount;
32            }
33        }
34      
35        return specialCount;
36    }
37}
38
1class Solution {
2public:
3    int numberOfSpecialChars(std::string word) {
4        // Arrays to store the first and last occurrence of each character
5        std::vector<int> firstOccurrence('z' + 1, 0);
6        std::vector<int> lastOccurrence('z' + 1, 0);
7
8        // Traverse through the word to record the first and last positions of each character
9        for (int i = 1; i <= word.size(); ++i) {
10            int charIndex = word[i - 1]; // Get the ASCII value of the character at position i-1
11            if (firstOccurrence[charIndex] == 0) {
12                firstOccurrence[charIndex] = i; // Set the first occurrence if not set before
13            }
14            lastOccurrence[charIndex] = i; // Always update the last occurrence
15        }
16
17        int ans = 0;
18
19        // Iterate over lowercase English letters
20        for (int i = 0; i < 26; ++i) {
21            // Check if the last occurrence of a lowercase letter is before the first occurrence of its uppercase counterpart
22            if (lastOccurrence['a' + i] && firstOccurrence['A' + i] && lastOccurrence['a' + i] < firstOccurrence['A' + i]) {
23                ++ans; // Increment the count of special characters
24            }
25        }
26        return ans; // Return the count of special characters
27    }
28};
29
1/**
2 * Function to count the number of special characters in a word.
3 * A special character is defined as a lowercase letter that appears before its corresponding uppercase letter.
4 * 
5 * @param word - The word to analyze.
6 * @returns The count of special characters.
7 */
8function numberOfSpecialChars(word: string): number {
9    // Arrays to store the first and last occurrences of each character
10    const firstOccurrence: number[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => 0);
11    const lastOccurrence: number[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => 0);
12
13    // Traverse the word to fill first and last occurrence for each character
14    for (let i = 0; i < word.length; ++i) {
15        const charCode = word.charCodeAt(i);
16      
17        // If this is the first time the character is encountered, update the first occurrence
18        if (firstOccurrence[charCode] === 0) {
19            firstOccurrence[charCode] = i + 1;
20        }
21        // Update the last occurrence
22        lastOccurrence[charCode] = i + 1;
23    }
24
25    let specialCharCount: number = 0;
26
27    // Loop through all possible lowercase letters
28    for (let i = 0; i < 26; ++i) {
29        const lowercaseCharCode = 'a'.charCodeAt(0) + i;
30        const uppercaseCharCode = 'A'.charCodeAt(0) + i;
31
32        // Check if a lowercase letter occurs before its corresponding uppercase letter
33        if (
34            lastOccurrence[lowercaseCharCode] &&
35            firstOccurrence[uppercaseCharCode] &&
36            lastOccurrence[lowercaseCharCode] < firstOccurrence[uppercaseCharCode]
37        ) {
38            ++specialCharCount;
39        }
40    }
41
42    return specialCharCount;
43}
44

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 is because the function iterates through the string to build the first and last dictionaries, which takes O(n) time, and then it performs a constant time operation for each pair of lowercase and uppercase letters, which is O(|\Sigma|).

The space complexity is O(|\Sigma|) since the first and last dictionaries are used to store each unique character in word, and the maximum number of unique characters is limited by |\Sigma|. In this context, |\Sigma| = 128 since the problem suggests it is the size of the character set considered.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More