Count the Number of Special Characters II
Source: leetcode
Difficulty: Medium
Tags: hash-table, string

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** lettersin`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.




C++ solution:
class Solution {
public:
  int numberOfSpecialChars(string word) {
    ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int ans = 0;
    vector<int> lower(26, -1), upper(26,-1);
    for(int i = 0; i < word.size(); i++){
      if(word[i] >= 97) lower[word[i]-97] = i;
      if(word[i] < 97 && upper[word[i]-65] == -1) upper[word[i]-65] = i;
    }
    for(int i = 0; i < 26; i++){
      if(lower[i] == -1 || upper[i] == -1) continue;
      if(lower[i] < upper[i]) ans++;
    }
    return ans;
  }
};

Go solution:
var ALPHABET_SIZE = 26
var VISITED int = math.MaxInt

func numberOfSpecialChars(word string) int {
	lastIndexSmallLetters := createArrayLastIndexSmallLetters(&word)
	return findNumberOfSpecialChars(&word, &lastIndexSmallLetters)
}

func createArrayLastIndexSmallLetters(word *string) []int {
	lastIndexSmallLetters := make([]int, ALPHABET_SIZE)
	for i := range lastIndexSmallLetters {
		lastIndexSmallLetters[i] = VISITED
	}

	for i := range *word {
		letter := (*word)[i]
		if letter >= 'a' {
			lastIndexSmallLetters[letter-'a'] = i
		}
	}

	return lastIndexSmallLetters
}

func findNumberOfSpecialChars(word *string, lastIndexSmallLetters *[]int) int {
	numberOfSpecialChars := 0

	for i := range *word {
		letter := (*word)[i]
		if letter >= 'a' {
			continue
		}
		if (*lastIndexSmallLetters)[letter-'A'] < i {
			numberOfSpecialChars++
		}
		(*lastIndexSmallLetters)[letter-'A'] = VISITED
	}

	return numberOfSpecialChars
}

Java solution:
class Solution {
    public int numberOfSpecialChars(String word) {
        int a[][] = new int[26][2];
        int b[][] = new int[26][2];
        for(int i=0;i<26;i++)
        {
            b[i][1]=-1;
        }
        for(int i=0;i<word.length();i++)
        {
            char c = word.charAt(i);
            if(c>='a' && c<='z')
            {
                a[c-'a'][0]++;
                a[c-'a'][1]=i;
            }
            else
            {
                b[c-'A'][0]++;
                if(b[c-'A'][1] == -1)
                {
                    b[c-'A'][1]=i;
                }
            }
        }
        int count=0;
        for(int i=0;i<26;i++)
        {
            if(a[i][0] != 0 && b[i][0] != 0 && a[i][1] < b[i][1])
            {
                count++;
            }
        }
        return count;
    }
}

JavaScript solution:
var numberOfSpecialChars = function (word) {
    const firstUppercase = new Set();
    const lastLowercase = new Set();

    for (let i = 0; i < word.length; i++) {
        const char = word[i];
        if (char >= 'a' && char <= 'z') {
            if (!(char in lastLowercase)) {
                lastLowercase[char] = i;
            } else {
                lastLowercase[char] = Math.max(lastLowercase[char], i);
            }
        } else if (char >= 'A' && char <= 'Z') {
            const lowerChar = char.toLowerCase();
            if (!(lowerChar in firstUppercase)) {
                firstUppercase[lowerChar] = i;
            }
        }
    }

    let count = 0;
    for (const char in lastLowercase) {
        if (char in firstUppercase) {
            if (lastLowercase[char] < firstUppercase[char]) {
                count++;
            }
        }
    }

    return count;
};

Python solution:
class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        count = 0
        for c in 'abcdefghijklmnopqrstuvwxyz':
            if c in word and word.rfind(c) < word.find(c.upper()):
                count += 1
        
        return count

Ruby solution:
def number_of_special_chars w
    l, u = 2.times.map { [false] * 26 }
    for c in w.each_byte
        c > 96 ?
            (l[c - 97] = !u[c - 97]) :
            (u[c - 65] = true)
    end
    26.times.count { l[_1] && u[_1] }
end