LeetCode 3120 - Count the Number of Special Characters I

The problem asks us to count the number of special characters in a given string word. A character is defined as special if it appears in both lowercase and uppercase forms within the same string.

leetcodeeasyhash-tablestring

LeetCode Problem 3120

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem asks us to count the number of special characters in a given string word. A character is defined as special if it appears in both lowercase and uppercase forms within the same string. For example, if 'a' appears as both 'a' and 'A' anywhere in word, then 'a' counts as a special character.

The input word is a string consisting only of English letters (both lowercase and uppercase) and has a length between 1 and 50. The output is a single integer, the count of special letters.

Key points to understand include that we only care about letters that appear in both cases. Letters that appear only in lowercase or only in uppercase are ignored. Since the string length is small (maximum 50), efficiency is not a primary concern, but we can still apply a clean, hash-based solution. Edge cases include strings with no uppercase letters, no lowercase letters, or repeated letters in only one case.

Approaches

The brute-force approach would involve iterating through each character and, for every lowercase letter, scanning the string to see if its uppercase counterpart exists, and vice versa. While this would produce the correct answer, it involves scanning the string repeatedly and has a worst-case time complexity of O(n^2), which is unnecessary even for short strings.

The optimal approach uses two sets: one to track lowercase letters and one to track uppercase letters. By building these sets in a single pass, we can then compute the intersection between the lowercase set and the lowercase version of the uppercase set to determine the special characters. This method is simple, clear, and runs in linear time relative to the length of the string.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) For each character, check if its counterpart exists
Optimal O(n) O(1) Use two sets to track lowercase and uppercase letters and compute intersection

Algorithm Walkthrough

  1. Initialize two empty sets: lower_set to store lowercase letters, and upper_set to store uppercase letters.
  2. Iterate over each character ch in the string word.
  3. If ch is lowercase, add it to lower_set.
  4. If ch is uppercase, add it to upper_set.
  5. Convert every element in upper_set to lowercase and compute the intersection with lower_set. This gives all letters that appear in both cases.
  6. Return the size of the intersection set as the result.

Why it works: The sets efficiently track which characters appear in each case. By converting uppercase letters to lowercase and computing the intersection, we ensure that we only count letters appearing in both cases exactly once. This guarantees correctness.

Python Solution

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        lower_set = set()
        upper_set = set()
        
        for ch in word:
            if ch.islower():
                lower_set.add(ch)
            elif ch.isupper():
                upper_set.add(ch)
        
        special_chars = lower_set.intersection({ch.lower() for ch in upper_set})
        return len(special_chars)

This code first collects all lowercase and uppercase letters into separate sets. It then converts the uppercase letters to lowercase and finds the intersection with the lowercase set. The size of this intersection is exactly the number of special characters.

Go Solution

func numberOfSpecialChars(word string) int {
    lowerSet := make(map[rune]struct{})
    upperSet := make(map[rune]struct{})
    
    for _, ch := range word {
        if ch >= 'a' && ch <= 'z' {
            lowerSet[ch] = struct{}{}
        } else if ch >= 'A' && ch <= 'Z' {
            upperSet[ch] = struct{}{}
        }
    }
    
    count := 0
    for ch := range upperSet {
        lowerCh := ch + ('a' - 'A')
        if _, exists := lowerSet[lowerCh]; exists {
            count++
        }
    }
    
    return count
}

In Go, we use maps as sets. The conversion from uppercase to lowercase is done using ASCII arithmetic ('a' - 'A'). We then check for each uppercase letter if the corresponding lowercase exists in lowerSet.

Worked Examples

Example 1: word = "aaAbcBC"

Step lower_set upper_set special_chars
Initial {} {} {}
'a' {'a'} {} {}
'a' {'a'} {} {}
'A' {'a'} {'A'} {}
'b' {'a', 'b'} {'A'} {}
'c' {'a', 'b', 'c'} {'A'} {}
'B' {'a', 'b', 'c'} {'A', 'B'} {}
'C' {'a', 'b', 'c'} {'A', 'B', 'C'} {'a', 'b', 'c'}
Result - - 3

Example 2: word = "abc"

Lowercase set = {'a', 'b', 'c'}, Uppercase set = {} → intersection = {} → result = 0

Example 3: word = "abBCab"

Lowercase set = {'a', 'b', 'c'}, Uppercase set = {'B', 'C'} → intersection = {'b'} → result = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the string to build sets, plus intersection of small sets
Space O(1) Maximum 26 lowercase and 26 uppercase letters can be stored in sets, constant space

The algorithm is efficient because it leverages set operations, which are O(1) for insertion and membership checks. Even though two sets are used, the maximum size is capped at 26, making it effectively constant space.

Test Cases

# Provided examples
assert Solution().numberOfSpecialChars("aaAbcBC") == 3  # multiple special characters
assert Solution().numberOfSpecialChars("abc") == 0     # no uppercase letters
assert Solution().numberOfSpecialChars("abBCab") == 1  # only 'b' is special

# Edge cases
assert Solution().numberOfSpecialChars("A") == 0       # single uppercase, no match
assert Solution().numberOfSpecialChars("a") == 0       # single lowercase, no match
assert Solution().numberOfSpecialChars("Aa") == 1      # one special character
assert Solution().numberOfSpecialChars("aAbBcCdDeEfF") == 6  # all letters special
assert Solution().numberOfSpecialChars("abcdefghijklmnopqrstuvwxyz") == 0 # all lowercase
assert Solution().numberOfSpecialChars("ABCDEFGHIJKLMNOPQRSTUVWXYZ") == 0 # all uppercase
Test Why
"aaAbcBC" Tests multiple letters appearing in both cases
"abc" Tests string with no uppercase letters
"abBCab" Tests string where only some letters are special
"A", "a" Tests single-character strings
"Aa" Minimal special character case
"aAbBcCdDeEfF" Tests multiple special characters
all lowercase/uppercase Tests case with no possible special characters

Edge Cases

One edge case is a string of length 1, either lowercase or uppercase. Since there is no counterpart, the result must be 0. Another edge case is when all letters appear only in one case (all lowercase or all uppercase). The intersection will be empty, producing 0, which is correct. Finally, the case where every letter appears in both cases should correctly return the count equal to the number of distinct letters, which tests that the intersection logic handles multiple letters correctly. All these are handled by our set-based implementation.