After a hard day Vitaly got very hungry and he wants to eat his favorite potato pie. But it's not that simple. Vitaly is in the first room of the house with n room located in a line and numbered starting from one from left to right. You can go from the first room to the second room, from the second room to the third room and so on — you can go from the (n - 1)-th room to the n-th room. Thus, you can go to room x only from room x - 1.
The potato pie is located in the n-th room and Vitaly needs to go there.
Each pair of consecutive rooms has a door between them. In order to go to room x from room x - 1, you need to open the door between the rooms with the corresponding key.
In total the house has several types of doors (represented by uppercase Latin letters) and several types of keys (represented by lowercase Latin letters). The key of type t can open the door of type T if and only if t and T are the same letter, written in different cases. For example, key f can open door F.
Each of the first n - 1 rooms contains exactly one key of some type that Vitaly can use to get to next rooms. Once the door is open with some key, Vitaly won't get the key from the keyhole but he will immediately run into the next room. In other words, each key can open no more than one door.
Vitaly realizes that he may end up in some room without the key that opens the door to the next room. Before the start his run for the potato pie Vitaly can buy any number of keys of any type that is guaranteed to get to room n.
Given the plan of the house, Vitaly wants to know what is the minimum number of keys he needs to buy to surely get to the room n, which has a delicious potato pie. Write a program that will help Vitaly find out this number.
The first line of the input contains a positive integer n (2 ≤ n ≤ 105) — the number of rooms in the house.
The second line of the input contains string s of length 2·n - 2. Let's number the elements of the string from left to right, starting from one.
The odd positions in the given string s contain lowercase Latin letters — the types of the keys that lie in the corresponding rooms. Thus, each odd position i of the given string s contains a lowercase Latin letter — the type of the key that lies in room number (i + 1) / 2.
The even positions in the given string contain uppercase Latin letters — the types of doors between the rooms. Thus, each even position iof the given string s contains an uppercase letter — the type of the door that leads from room i / 2 to room i / 2 + 1.
Print the only integer — the minimum number of keys that Vitaly needs to buy to surely get from room one to room n.
3
aAbB
0
4
aBaCaB
3
5
xYyXzZaZ
2
*****************************************************
题意说明：
n个房间排成一排，每个房间里有一把钥匙，房间之间有门，大写字母代表门小写字母代表钥匙，对应的字母可以打开对应的门，从左到右，要从第一个房间到达地n个房间，问需要买几把钥匙（到达一个房间可以拿到其中的钥匙，钥匙只能使用一次，如果手中没有能打开这个门的钥匙可以购买）。
******************************************************
这一题暴力来做，有 n^2 的算法，就是直接对于每个门检查手里的钥匙，判断是否购买；但是这样做超时，我第一次就是这样做的，没有经验就直接上了，结果超时。
有 O(n) 的算法，对于这样的只有大小写字母组成的字符串，并且是配对操作的基本上都有这样的一个做法，就是开一个26的数组，记录每个字幕的次数；
这一题中，碰到小写字幕就将小写字母数加一，碰到大写就检查是否有对应的小写字母，如果没有就要购买了，如果有，就减一，相当于消耗了一把该钥匙；
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<string> 6 #include<cstring> 7 #include<vector> 8 using namespace std; 9 char a[200010]; 10 int n,ans=0,t[26]={0}; 11 int main() 12 { 13 scanf("%d",&n); 14 scanf("%s",a); 15 for(int i=0;i<2*n-2;i+=2) 16 { 17 t[a[i]-'a']++; 18 if(t[a[i+1]-'A']<=0) 19 ans++; 20 else 21 t[a[i+1]-'A']--; 22 } 23 printf("%d ",ans); 24 return 0; 25 }