4303: 「POI2012」字母 Letters

内存限制:128 MB 时间限制:0.500 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

**译自 POI 2012 Stage 1. 「[Letters](https://szkopul.edu.pl/problemset/problem/7u_14yXL3mR3mO0seZLusF5U/site/?key=statement)」** 给定两个长度相同且由大写英文字母组成的字符串 A 和 B,保证 A 和 B 中每种字母出现的次数相同。 每次可以交换 A 中相邻两个字符,求最少需要交换多少次可以使得 A 变成 B。

输入

第一行一个正整数 $n (2 \le n \le 1\ 000\ 000)$,表示字符串的长度。 第二行和第三行各一个长度为 $n$ 的字符串,并且只包含大写英文字母。

输出

一个非负整数,表示最少的交换次数。

样例输入 复制

3
ABC
BCA

样例输出 复制

2

提示


数据范围:对于 $30\%$ 的数据保证 $n \le 1000$. 对于所有数据保证 $2 \le n \le 1\ 000\ 000$. Task author: Marian M. Kedzierski.

来源/分类