#Pbit110. 4.秘密邮件

    ID: 179 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>树状数组赛制:OI来源:wyfoj http://127.0.0.1

4.秘密邮件

4.秘密邮件

题目描述

小明收到了一封来自外星球的秘密邮件。邮件由n个大写英文字母组成, 不巧的是小明收到邮件以后一不小心打乱了原来的字母顺序。但是聪明的小明记住了原邮件的完整内容,现在她每次可以选择打乱后的邮件中相邻的两个字母进行交换,问最少交换多少次能够将打乱的邮件恢复成原邮件。

输入格式

第一行一个整数n表示邮件的长度。

第二行一个长度为n的只包含大写字母的字符串表示打乱后的邮件。第三行一个长度为n的只包含大写字母的字符串表示原邮件。

为保证打乱后的邮件可以恢复成原邮件,所有的测试数据满足任意一种大写字母在两封邮件中的出现次数相同。

输出格式

共一行包含一个整数,表示最少的交换次数。

数据范围

(原站未提供,导入后需人工补齐)

样例

4
ABCD
DBCA
5

提示

样例解释

第一次交换第一个和第二个字母得到BACD;

第二次交换第二个和第三个字母得到BCAD;

第三次交换第三个和第四个字母得到BCDA;

第四次交换第二个和第三个字母得到BDCA;

第五次交换第一个和第二个字母得到DBCA。

对于100对于100%的数据,满足1<=n<=10^6