Problem : 126 - 交換字卡

Problem Statistics

Solved Member: 29　　Submission: 67　　User Tried: 29

Statement:

小強尼有一個非常長的姓，他發現跟他同一個幼稚園裡也有一個叫瑪麗的人跟他有同樣長的姓氏。不只如此，他還發現他們兩個人姓氏的字母數是相同的，有同樣多個A,同樣多個B ... ，僅僅是排列順序不同而已。

某天，強尼與瑪麗在課堂中將他們的姓用字卡排出來。瑪麗決定與強尼玩一個遊戲，強尼每次可以將他姓氏中相鄰的字卡交換，強尼必須在最少的交換次數下將字卡的順序變成瑪麗的姓。

當然這個問題對一個幼稚園的小朋友來說太難了，於是強尼決定請你，幼稚園中最優秀的程式設計師，來解決這個難題。

Input:Output:

第 1 行有一個正整數 N(2 ≤ N ≤ 1000000)，代表強尼與瑪麗的姓是由 N 個字母組成。
第 2 行有一個長度 N 的字串，代表強尼的姓。
第 3 行有一個長度 N 的字串，代表瑪麗的姓。
這兩個姓氏皆是由大寫字母所組成。

輸出一個數字，代表強尼最少要交換幾次才能夠達成任務。

Sample Input:Sample Output:

3
ABC
BCA

HINT:

30%的測資滿足：N ≤ 1000

Source:

POI 19 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-ocen	1000ms	131072kb
1	1000ms	131072kb	10
2-ocen	1000ms	131072kb
2	1000ms	131072kb	10
3-ocen	1000ms	131072kb
3-1	1000ms	131072kb	10
3-2	1000ms	131072kb
4-ocen	1000ms	131072kb
4-1	1000ms	131072kb	10
4-2	1000ms	131072kb
5-ocen	1000ms	131072kb
5-1	1000ms	131072kb	10
5-2	1000ms	131072kb
6-1	1000ms	131072kb	10
6-2	1000ms	131072kb
7-1	3000ms	131072kb	10
7-2	3000ms	131072kb
8-1	4000ms	131072kb	10
8-2	4000ms	131072kb
9-1	6000ms	131072kb	10
9-2	6000ms	131072kb
10-1	6000ms	131072kb	10
10-2	6000ms	131072kb