Minimum Adjacent Swaps to Transform

You are given two strings source and target of the same length. target is guaranteed to be a permutation of source: both strings contain the same characters with the same frequencies.

In one operation you may swap two adjacent characters of source.

Return the minimum number of operations required to transform source into target.

Note that the answer can exceed the 32-bit integer range.

Examples

Example 1

Input: source = "GUM", target = "MUG"
Output: 3
Explanation: One optimal sequence is "GUM" -> "GMU" (swap positions 1 and 2) -> "MGU" (swap positions 0 and 1) -> "MUG" (swap positions 1 and 2). No sequence of fewer than 3 adjacent swaps works.

Example 2

Input: source = "ABAB", target = "BABA"
Output: 2
Explanation: "ABAB" -> "BAAB" (swap positions 0 and 1) -> "BABA" (swap positions 2 and 3). With duplicate letters, matching each occurrence to the nearest available occurrence in target keeps the swap count at 2.