CF525A Vitaliy and Pie

劳累一天后，Vitaly 十分饥饿，他想吃他最喜欢的土豆馅饼。但事情没有那么简单。Vitaly 现在位于一排 $n$ 个房间的第一个房间中，这些房间从左到右依次编号为 1 到 $n$。你只能从第 $1$ 个房间前往第 $2$ 个房间，从第 $2$ 个房间前往第 $3$ 个房间，以此类推 —— 也就是说，只能从第 $x-1$ 个房间进入第 $x$ 个房间。 土豆馅饼就在第 $n$ 个房间里，Vitaly 需要前往那里。 每对相邻的房间之间都有一扇门。想要从第 $x-1$ 个房间进入第 $x$ 个房间，你需要使用相应的钥匙打开两房之间的门。 整个房子有多种类型的门（用大写英文字母表示）和多种类型的钥匙（用小写英文字母表示）。一把 $t$ 类型的钥匙可以打开 $T$ 类型的门，当且仅当 $t$ 和 $T$ 为同一个字母，大小写不同。例如，钥匙 f 可以打开门 F。 在前 $n-1$ 个房间里，每个房间恰好有一种类型的钥匙，Vitaly 可以用它去打开通往后续房间的门。一旦门被某个钥匙打开，这把钥匙会留在钥匙孔里，Vitaly 会立刻进入下一个房间。换句话说，每把钥匙最多只能打开一扇门。 Vitaly 意识到他可能会因为缺少打开下一个房间门的钥匙而被困在某个房间。在开始向土豆馅饼进发前，Vitaly 可以购买任意数量的任意类型的钥匙，只要能够保证他能顺利到达第 $n$ 个房间即可。 给出房屋的平面图，请你告诉 Vitaly，他至少需要购买多少把钥匙才能保证一定能到达有美味土豆馅饼的第 $n$ 个房间。请写一个程序帮助 Vitaly 计算这个数。

输入的第一行包含一个正整数 $n$（$2 \leq n \leq 10^5$），表示房间的数量。 输入的第二行包含一个长度为 $2n-2$ 的字符串 $s$。编号从 1 开始，从左到右。 字符串 $s$ 的奇数位是小写英文字母，表示对应房间内摆放的钥匙类型。因此，$s$ 的第 $i$ 个奇数位（$i$ 为奇数）表示编号为 $(i+1)/2$ 的房间里的钥匙类型。 字符串 $s$ 的偶数位是大写英文字母，表示房间之间的门的类型。因此，$s$ 的第 $i$ 个偶数位（$i$ 为偶数）表示从房间 $i/2$ 通往房间 $i/2+1$ 的门的类型。

输出唯一的一个整数，表示 Vitaly 至少需要购买多少把钥匙，才能保证顺利从第一个房间走到第 $n$ 个房间。

由 ChatGPT 5 翻译