Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: word = "aaAbcBC"

Output: 3

Explanation:

The special characters are `'a'`, `'b'`, and `'c'`.

Example 2

1
2
3
4
5
6
7
8


Input: word = "abc"

Output: 0

Explanation:

There are no special characters in `word`.

Example 3

1
2
3
4
5
6
7
8


Input: word = "AbBCab"

Output: 0

Explanation:

There are no special characters in `word`.

Constraints

  • 1 <= word.length <= 2 * 10^5
  • word consists of only lowercase and uppercase English letters.

Solution

Method 1 – Index Tracking and Set Check

Intuition

A letter is special if both its lowercase and uppercase forms appear, and all lowercase occurrences come before the first uppercase occurrence. We can track the last index of each lowercase and the first index of each uppercase, then check the order.

Approach

  1. For each letter ‘a’ to ‘z’, track:
    • The last index of its lowercase occurrence (lastLower)
    • The first index of its uppercase occurrence (firstUpper)
  2. Iterate through the string and update these indices.
  3. For each letter, if both indices are set and all lowercase indices are before the first uppercase, count it as special.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numberOfSpecialChars(string word) {
        vector<int> lastLower(26, -1), firstUpper(26, -1);
        int n = word.size();
        for (int i = 0; i < n; ++i) {
            char c = word[i];
            if (islower(c)) lastLower[c - 'a'] = i;
            else if (isupper(c) && firstUpper[c - 'A'] == -1) firstUpper[c - 'A'] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) ++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

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

class Solution {
    public int numberOfSpecialChars(String word) {
        int[] lastLower = new int[26];
        int[] firstUpper = new int[26];
        Arrays.fill(lastLower, -1);
        Arrays.fill(firstUpper, -1);
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (Character.isLowerCase(c)) lastLower[c - 'a'] = i;
            else if (Character.isUpperCase(c) && firstUpper[c - 'A'] == -1) firstUpper[c - 'A'] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun numberOfSpecialChars(word: String): Int {
        val lastLower = IntArray(26) { -1 }
        val firstUpper = IntArray(26) { -1 }
        for ((i, c) in word.withIndex()) {
            if (c.isLowerCase()) lastLower[c - 'a'] = i
            else if (c.isUpperCase() && firstUpper[c - 'A'] == -1) firstUpper[c - 'A'] = i
        }
        var ans = 0
        for (i in 0 until 26) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && lastLower[i] < firstUpper[i]) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        last_lower = [-1] * 26
        first_upper = [-1] * 26
        for i, c in enumerate(word):
            if c.islower():
                last_lower[ord(c) - ord('a')] = i
            elif c.isupper() and first_upper[ord(c) - ord('A')] == -1:
                first_upper[ord(c) - ord('A')] = i
        ans = 0
        for i in range(26):
            if last_lower[i] != -1 and first_upper[i] != -1 and last_lower[i] < first_upper[i]:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn number_of_special_chars(word: String) -> i32 {
        let mut last_lower = vec![-1; 26];
        let mut first_upper = vec![-1; 26];
        for (i, c) in word.chars().enumerate() {
            if c.is_ascii_lowercase() {
                last_lower[(c as u8 - b'a') as usize] = i as i32;
            } else if c.is_ascii_uppercase() && first_upper[(c as u8 - b'A') as usize] == -1 {
                first_upper[(c as u8 - b'A') as usize] = i as i32;
            }
        }
        let mut ans = 0;
        for i in 0..26 {
            if last_lower[i] != -1 && first_upper[i] != -1 && last_lower[i] < first_upper[i] {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    numberOfSpecialChars(word: string): number {
        const lastLower = Array(26).fill(-1)
        const firstUpper = Array(26).fill(-1)
        for (let i = 0; i < word.length; ++i) {
            const c = word[i]
            if (c >= 'a' && c <= 'z') lastLower[c.charCodeAt(0) - 97] = i
            else if (c >= 'A' && c <= 'Z' && firstUpper[c.charCodeAt(0) - 65] === -1) firstUpper[c.charCodeAt(0) - 65] = i
        }
        let ans = 0
        for (let i = 0; i < 26; ++i) {
            if (lastLower[i] !== -1 && firstUpper[i] !== -1 && lastLower[i] < firstUpper[i]) ans++
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string, as we scan the string and check 26 letters.
  • 🧺 Space complexity: O(1) since the arrays are of fixed size 26.