4.秘密邮件

题目描述

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

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

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

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

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

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

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^{6}$ 。

4
ABCD
DBCA

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

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

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

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

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