← 返回题目列表

Codeforces · 525/A

A. 维塔利和派

中文机器翻译题面 查看原题

经过辛苦的一天后,维塔利非常饿,他想吃他最喜欢的土豆派。但事情没那么简单。维塔利在房子的第一个房间里,有n个房间排成一排,从左到右从一个开始编号。你可以从第一个房间到第二个房间,从第二个房间到第三个房间,依此类推——你可以从第 (n - 1) 个房间到第 n 个房间。因此,您只能从房间 x - 1 前往房间 x。

土豆派位于第n个房间,维塔利需要去那里。

每对连续的房间之间都有一扇门。为了从房间x - 1去房间x,你需要用相应的钥匙打开房间之间的门。

房子总共有几种类型的门(用大写拉丁字母表示)和几种类型的钥匙(用小写拉丁字母表示)。当且仅当 t 和 T 是同一个字母,但写法不同时,t 类型的钥匙才能打开 T 类型的门。例如,钥匙f可以打开门F。

前 n - 1 个房间中的每一个都恰好包含一把某种类型的钥匙,Vitaly 可以使用它进入下一个房间。一旦用钥匙打开门,维塔利不会从钥匙孔中拿到钥匙,但他会立即跑进隔壁房间。换句话说,每把钥匙只能打开一扇门。

维塔利意识到他最终可能会进入某个房间,却没有打开下一个房间门的钥匙。在开始争夺土豆派之前,维塔利可以购买任意数量、任意类型的钥匙,以保证到达 n 号房间。

考虑到房子的平面图,Vitaly 想知道他至少需要购买多少把钥匙才能确保到达 n 号房间,那里有美味的土豆饼。编写一个程序来帮助维塔利找出这个数字。

输入

输入的第一行包含一个正整数 n (2 ≤ n ≤ 105) — 房子的房间数。

输入的第二行包含长度为 2·n - 2 的字符串 s。让我们从左到右对字符串的元素进行编号,从 1 开始。

给定字符串 s 中的奇数位置包含小写拉丁字母——相应房间中钥匙的类型。因此,给定字符串 s 的每个奇数位置 i 都包含一个小写拉丁字母——房间号 (i + 1) / 2 中钥匙的类型。

给定字符串中的偶数位置包含大写拉丁字母 - 房间之间的门的类型。因此,给定字符串 s 的每个偶数位置 i 都包含一个大写字母——从房间 i / 2 通向房间 i / 2 + 1 的门的类型。

输出

打印唯一的整数——Vitaly 需要购买的钥匙的最小数量才能确保从 1 号房间到达 n 号房间。

示例

输入 #1

3
aAbB

输出 #1

0

输入 #2

4
aBaCaB

输出 #2

3

输入 #3

5
xYyXzZaZ

输出 #3

2