P3531 [POI 2012] LIT-Letters

Given two strings $a$, $b$ of equal length, each consisting only of uppercase letters, you may swap two adjacent characters in $a$ at a time. Find the minimum number of swaps needed so that the string obtained from $a$ becomes identical to $b$.

The first line contains an integer $n$, the length of the strings. The second line contains a string of length $n$, denoting $a$. The third line contains a string of length $n$, denoting $b$.

Output a single integer on one line, the minimum number of swaps.

#### Constraints - For 30% of the testdata, it is guaranteed that $n \leq 10^3$. - For 100% of the testdata, $1 \leq n \leq 10^6$, $a$, $b$ contain only uppercase letters, and the testdata guarantees that $a$ can be transformed into $b$. Translated by ChatGPT 5