这是一个简单而有效的解决方案：
让
Q[ s2[i] ] = the positions character s2[i] is on in s2。让
P[i] = on whatposition is the character corresponding to s1[i] in the second string。
建立Q和P：
for ( int i = 0; i < s1.size(); ++i ) Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of liststemp[0 .. 25] = {0}for ( int i = 0; i < s1.size(); ++i ) P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];例：
1234s1: abcds2: acdbQ: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2 P[4] = 3P具有
2反转（
4 2和
4 3），所以这就是答案。
此解决方案是
O(n log n)因为构建
P和
Q可以在其中完成，
O(n)而归并排序可以计算中的反转
O(n log n)。
