Leetcode 3121: Count the Number of Special Characters II
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.Problem
Approach
Steps
Complexity
Input: The input consists of a string `word` of length n.
Example: word = "abcABca"
Constraints:
• 1 <= word.length <= 2 * 10^5
• word consists of only lowercase and uppercase English letters
Output: Return the number of special letters in the string `word`.
Example: Output: 2
Constraints:
Goal: Identify letters that appear in both lowercase and uppercase in the string and check if every lowercase occurrence precedes the first uppercase occurrence.
Steps:
• 1. Initialize a vector of size 26 to keep track of the occurrences of each letter in `word`.
• 2. Loop through the string and update the vector to mark the status of each character.
• 3. After processing the string, check which letters have both lowercase and uppercase occurrences where all lowercase letters precede the uppercase ones.
• 4. Count and return the total number of such special letters.
Goal: The problem constraints define the limits on the length and content of the string.
Steps:
• 1 <= word.length <= 2 * 10^5
• word consists of only lowercase and uppercase English letters
Assumptions:
• The input string will only contain lowercase and uppercase English letters.
• The string will have a length between 1 and 2 * 10^5 characters.
• Input: word = "abcABca"
• Explanation: The special characters are 'a' and 'b', because they appear in both lowercase and uppercase, and all lowercase occurrences precede the uppercase ones.
• Input: word = "hello"
• Explanation: No special characters exist in this string, as no letter appears in both uppercase and lowercase.
• Input: word = "AaaBcAB"
• Explanation: The letter 'a' appears both in lowercase and uppercase, but the lowercase 'a' occurs after the uppercase 'A', so it's not special.
Approach: We can solve this problem by iterating through the string, marking occurrences of each character in a vector, and then checking the conditions for special letters.
Observations:
• We need to check the order of lowercase and uppercase occurrences of each letter.
• By using a vector to track the occurrences and then validating the conditions for each letter, we can efficiently solve the problem.
Steps:
• 1. Initialize a vector of size 26 to store the status of each character.
• 2. Traverse the string and update the vector based on whether the character is lowercase or uppercase.
• 3. After processing the string, check each letter to ensure its lowercase occurrences appear before any uppercase occurrences.
• 4. Count the number of special letters and return the result.
Empty Inputs:
• The input will always have at least one character, as per the problem constraints.
Large Inputs:
• The solution should efficiently handle strings of up to 2 * 10^5 characters.
Special Values:
• If the string contains only lowercase or only uppercase letters, the output should be 0.
Constraints:
• The string consists only of lowercase and uppercase English letters.
int numberOfSpecialChars(string word) {
vector<int> ch(26, 0);
for(char x: word) {
if(isupper(x)) {
if(ch[x - 'A'] == -1) continue;
if(ch[x - 'A'] != 1 && ch[x - 'A'] != 2) {
ch[x - 'A'] = -1;
continue;
}
ch[x - 'A'] = 2;
} else {
if(ch[x - 'a'] == -1) continue;
if(ch[x - 'a'] == 2) {
ch[x - 'a'] = -1;
continue;
}
ch[x - 'a'] = 1;
}
// cout << x << " ";
// for(int i = 0; i < 26; i++) {
// cout << ch[i] << " ";
// }
// cout << "\n";
}
int cnt = 0;
for(int i = 0; i < 26; i++) {
// cout << ch[i] << " ";
if(ch[i] == 2)
cnt++;
}
return cnt;
}
1 : Function Definition
int numberOfSpecialChars(string word) {
Defines the function `numberOfSpecialChars` that takes a string `word` as input and returns the count of special characters, where a special character is a pair of the same letter in both lowercase and uppercase.
2 : Array Initialization
vector<int> ch(26, 0);
Initializes a vector `ch` of size 26 to keep track of the status of each letter. The vector elements will hold values representing the status of each character (0 = not encountered, 1 = lowercase encountered, 2 = uppercase encountered, -1 = both encountered and invalid).
3 : Loop Through String
for(char x: word) {
Iterates through each character `x` in the string `word`.
4 : Check Uppercase Character
if(isupper(x)) {
Checks if the current character `x` is uppercase.
5 : Handle Invalid Uppercase
if(ch[x - 'A'] == -1) continue;
If the uppercase version of the character has already been invalidated, skips to the next character.
6 : Check Uppercase Validity
if(ch[x - 'A'] != 1 && ch[x - 'A'] != 2) {
Checks if the uppercase character has been encountered in an invalid state or hasn't been encountered yet.
7 : Invalidate Uppercase
ch[x - 'A'] = -1;
Marks the uppercase version of the character as invalid.
8 : Continue to Next Character
continue;
Skips to the next character in the loop if the current character has been invalidated.
9 : Mark Uppercase Valid
ch[x - 'A'] = 2;
Marks the uppercase version of the character as encountered and valid.
10 : Handle Lowercase Character
} else {
If the character is lowercase, execute the following logic for lowercase characters.
11 : Handle Invalid Lowercase
if(ch[x - 'a'] == -1) continue;
If the lowercase version of the character has already been invalidated, skips to the next character.
12 : Check Lowercase Validity
if(ch[x - 'a'] == 2) {
Checks if the lowercase character has been encountered in a valid state (both cases present).
13 : Invalidate Lowercase
ch[x - 'a'] = -1;
Marks the lowercase version of the character as invalid.
14 : Continue to Next Character
continue;
Skips to the next character in the loop if the current character has been invalidated.
15 : Set Lowercase to 1
ch[x - 'a'] = 1;
Marks the lowercase character as encountered.
16 : Count Special Characters
int cnt = 0;
Initializes the counter `cnt` to count the number of special characters (pairs of both uppercase and lowercase versions of the same letter).
17 : Loop Through Alphabet
for(int i = 0; i < 26; i++) {
Iterates through the `ch` array to count the special characters.
18 : Check Special Character
if(ch[i] == 2)
Checks if both uppercase and lowercase versions of the letter are present, which indicates a special character.
19 : Increment Counter
cnt++;
Increments the counter `cnt` when a special character is found.
20 : Return Result
return cnt;
Returns the total count of special characters.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the string. We process each character in the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only store information for each letter in a fixed-size vector.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus