Skip to content

3121. Count the Number of Special Characters II

SourceWeekly Contest 394 Q2DifficultyMediumRating1411

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.

 

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 * 105
  • word consists of only lowercase and uppercase English letters.

Solutions

Solution 1: Hash Table or Array

Thinking

Here every lowercase occurrence must also precede the first uppercase of that letter. Existence alone would accept a late lowercase.

It suffices to compare the last lowercase index with the first uppercase index, both obtainable in one scan.

Record \(first\) and \(last\) while walking \(word\), then count letters whose last lower index is strictly left of the first upper index.

We define two hash tables or arrays first and last to store the positions where each letter first appears and last appears respectively.

Then we traverse the string word, updating first and last.

Finally, we traverse all lowercase and uppercase letters. If last[a] exists and first[b] exists and last[a] < first[b], it means that the letter a is a special letter, and we increment the answer by one.

The time complexity is \(O(n + |\Sigma|)\), and the space complexity is \(O(|\Sigma|)\). Where \(n\) is the length of the string word, and \(|\Sigma|\) is the size of the character set. In this problem, \(|\Sigma| \leq 128\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        first, last = {}, {}
        for i, c in enumerate(word):
            if c not in first:
                first[c] = i
            last[c] = i
        return sum(
            a in last and b in first and last[a] < first[b]
            for a, b in zip(ascii_lowercase, ascii_uppercase)
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numberOfSpecialChars(String word) {
        int[] first = new int['z' + 1];
        int[] last = new int['z' + 1];
        for (int i = 1; i <= word.length(); ++i) {
            int j = word.charAt(i - 1);
            if (first[j] == 0) {
                first[j] = i;
            }
            last[j] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            int a = 'a' + i;
            int b = 'A' + i;
            if (last[a] > 0 && last[a] < first[b]) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numberOfSpecialChars(string word) {
        vector<int> first('z' + 1);
        vector<int> last('z' + 1);
        for (int i = 1; i <= word.size(); ++i) {
            int j = word[i - 1];
            if (first[j] == 0) {
                first[j] = i;
            }
            last[j] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (last['a' + i] && last['a' + i] < first['A' + i]) {
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func numberOfSpecialChars(word string) (ans int) {
    first := make([]int, 'z'+1)
    last := make([]int, 'z'+1)
    for i, c := range word {
        if first[c] == 0 {
            first[c] = i + 1
        }
        last[c] = i + 1
    }
    for i := 0; i < 26; i++ {
        if last['a'+i] > 0 && last['a'+i] < first['A'+i] {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function numberOfSpecialChars(word: string): number {
    const first: number[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => 0);
    const last: number[] = Array.from({ length: 'z'.charCodeAt(0) + 1 }, () => 0);
    for (let i = 0; i < word.length; ++i) {
        const j = word.charCodeAt(i);
        if (first[j] === 0) {
            first[j] = i + 1;
        }
        last[j] = i + 1;
    }
    let ans: number = 0;
    for (let i = 0; i < 26; ++i) {
        const a = 'a'.charCodeAt(0) + i;
        const b = 'A'.charCodeAt(0) + i;
        if (last[a] && last[a] < first[b]) {
            ++ans;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn number_of_special_chars(word: String) -> i32 {
        let mut first = [0; 128];
        let mut last = [0; 128];
        for (i, ch) in word.chars().enumerate() {
            let j = ch as u8 as usize;
            let pos = (i + 1) as i32;
            if first[j] == 0 {
                first[j] = pos;
            }
            last[j] = pos;
        }
        let mut ans = 0;
        for i in 0..26 {
            let a = (b'a' + i) as usize;
            let b = (b'A' + i) as usize;
            if last[a] > 0 && last[a] < first[b] {
                ans += 1;
            }
        }
        ans
    }
}

Comments