Minimum Adjacent Swaps — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Minimum Adjacent Swaps problem optimally.
O(n log n)O(n)Problem Description
Given two strings original and corrupted, where corrupted is guaranteed to be a subsequence of original, you may reorder the characters of corrupted by swapping any two adjacent characters. Each swap costs one unit. Your task is to compute the smallest total cost required to rearrange corrupted so that its characters appear in the same relative order as they do in original. In other words, after the swaps, the sequence of positions of the characters of corrupted inside original must be strictly increasing. Return that minimum number of adjacent swaps.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Adjacent Swaps"
WHY DOES IT MATTER?
Counting inversions is a fundamental pattern for problems that ask for the minimum number of adjacent operations to reach a target permutation, appearing in sorting, genome rearrangement, and UI animation optimizations.
OPTIMIZATION CHALLENGE
The key insight is to transform the string problem into a numeric permutation and then use a binary indexed tree to query and update prefix sums in logarithmic time, turning an O(n²) simulation into O(n log n).
REAL-WORLD CONNECTION
Think of a conveyor belt where packages must be reordered; each adjacent exchange costs time, and the total time equals how many package pairs are out of their final order – exactly the inversion count.
During an interview, first build the position‑mapping array, then immediately mention "inversion count" – interviewers love hearing the classic BIT/segment‑tree solution rather than re‑inventing a custom DP.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem reduces to measuring how far the current order of the subsequence is from its target order inside the original string. By scanning the original string and recording the positions of each character that appears in the corrupted string (taking care to match each occurrence uniquely), we obtain an integer array representing the desired ordering. The minimal number of adjacent swaps needed to transform one permutation into another equals the number of inversions in this array – each inversion corresponds to a pair of characters that are out of relative order and must cross each other once. A naïve simulation of swaps would be O(n²) and fails for lengths up to 10⁵, whereas counting inversions with a Fenwick Tree or a Segment Tree runs in O(n log n), which is optimal for this class of problems because any comparison‑based solution must inspect each element at least once.
Interview Questions on This Problem
Q1How would you compute the minimum adjacent swaps needed to transform a subsequence into its original ordering?
Map each character of the corrupted string to its next unused index in the original string, forming an index array, then count inversions in that array using a Fenwick Tree (or BIT) which gives the minimal swap count.
Q2Why does the inversion count equal the minimum number of adjacent swaps for this problem?
Each adjacent swap can resolve exactly one inversion by moving a larger index left of a smaller one; conversely, any out‑of‑order pair must be swapped at least once, so the total swaps needed equals the total inversions.
Q3Can this approach be extended to handle duplicate characters and still run in O(n log n)?
Yes; by processing the original string left‑to‑right and storing queues of positions for each character, we pop the front of the queue for each occurrence in the corrupted string, guaranteeing a unique mapping even with duplicates, after which the inversion count proceeds unchanged.
Examples
Input
original = "abcde", corrupted = "acb"
Output
1
Explanation: Map each character of corrupted to the earliest unused matching position in original: a→0, c→2, b→1, giving the index list [0,2,1]. To make the indices strictly increasing we need to swap the last two characters (c and b) once, resulting in the order a,b,c. Hence the minimum cost is 1.
Input
original = "aabbcc", corrupted = "bca"
Output
2
Explanation: Assign positions greedily: first b uses index 2, c uses index 4, a uses index 0, producing [2,4,0]. The list has two inversions: (2,0) and (4,0). Each inversion corresponds to one adjacent swap, so at least two swaps are necessary. One possible sequence: bca → bac (swap c and a) → abc (swap b and a). Total cost = 2.
Input
original = "zyxwvutsrq", corrupted = "zqr"
Output
1
Explanation: Corresponding positions: z→0, q→9, r→8 → [0,9,8]. Only the pair (9,8) is out of order, requiring a single adjacent swap of q and r. After swapping, the order becomes z r q, which follows the original order (indices 0,8,9). Minimum swaps = 1.
Constraints
- 1 <= original.length <= 200000
- 1 <= corrupted.length <= original.length
- original and corrupted contain only lowercase English letters
- corrupted is a subsequence of original
Optimal Approach & Strategy
Map characters to original indices, then count inversions of the resulting index array using a Fenwick Tree, achieving O(n log n) time.
Brute Force Approach
Simulate bubble‑sort style swaps on the corrupted string until it matches the original order, counting each swap – this is O(n²).
Code Solutions
/**
* @param {string} original
* @param {string} corrupted
* @return {number}
*/
var minimumAdjacentSwaps = function(original, corrupted) {
// Map each character in original to a queue of its indices
const charIndices = new Map();
for (let i = 0; i < original.length; i++) {
const c = original[i];
if (!charIndices.has(c)) {
charIndices.set(c, []);
}
charIndices.get(c).push(i);
}
// Get the target positions in original for each character in corrupted
const targetPositions = [];
for (const c of corrupted) {
const queue = charIndices.get(c);
targetPositions.push(queue.shift());
}
// Count the number of inversions in targetPositions using a Fenwick Tree
const n = targetPositions.length;
const bit = new Array(n + 1).fill(0);
const update = (idx) => {
while (idx <= n) {
bit[idx]++;
idx += idx & (-idx);
}
};
const query = (idx) => {
let sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
};
let inversions = 0;
for (let i = 0; i < n; i++) {
const pos = targetPositions[i];
inversions += i - query(pos);
update(pos);
}
return inversions;
};
console.log(minimumAdjacentSwaps("abcde", "acb"));#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
class Solution {
public:
int minimumAdjacentSwaps(const string& original, const string& corrupted) {
// Map each character in original to a queue of its indices
unordered_map<char, queue<int>> charIndices;
for (int i = 0; i < original.size(); ++i) {
charIndices[original[i]].push(i);
}
// Get the target positions in original for each character in corrupted
vector<int> targetPositions;
for (char c : corrupted) {
targetPositions.push_back(charIndices[c].front());
charIndices[c].pop();
}
// Count the number of inversions in targetPositions
// Use a Fenwick Tree (Binary Indexed Tree) for efficient inversion counting
int n = targetPositions.size();
vector<int> bit(n + 1, 0);
auto update = [&](int idx) {
while (idx <= n) {
bit[idx]++;
idx += idx & (-idx);
}
};
auto query = [&](int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
};
long long inversions = 0;
for (int i = 0; i < n; ++i) {
int pos = targetPositions[i];
// Number of elements already processed that have a position greater than pos
inversions += i - query(pos);
update(pos);
}
return (int)inversions;
}
};
int main() {
Solution sol;
string original = "abcde";
string corrupted = "acb";
cout << sol.minimumAdjacentSwaps(original, corrupted) << endl;
return 0;
}import java.util.*;
public class Solution {
public int minimumAdjacentSwaps(String original, String corrupted) {
// Map each character in original to a queue of its indices
Map<Character, Queue<Integer>> charIndices = new HashMap<>();
for (int i = 0; i < original.length(); i++) {
char c = original.charAt(i);
charIndices.computeIfAbsent(c, k -> new LinkedList<>()).add(i);
}
// Get the target positions in original for each character in corrupted
List<Integer> targetPositions = new ArrayList<>();
for (int i = 0; i < corrupted.length(); i++) {
char c = corrupted.charAt(i);
targetPositions.add(charIndices.get(c).poll());
}
// Count the number of inversions in targetPositions using a Fenwick Tree
int n = targetPositions.size();
int[] bit = new int[n + 1];
for (int i = 0; i < n; i++) {
int pos = targetPositions.get(i);
// Number of elements already processed that have a position greater than pos
int count = i - query(bit, pos);
// Add to inversions
// We need to accumulate, so use a long to avoid overflow
// But since we return int, we assume it fits
// For now, let's just compute and return
}
// Recompute properly
long inversions = 0;
for (int i = 0; i < n; i++) {
int pos = targetPositions.get(i);
inversions += i - query(bit, pos);
update(bit, pos, n);
}
return (int) inversions;
}
private void update(int[] bit, int idx, int n) {
while (idx <= n) {
bit[idx]++;
idx += idx & (-idx);
}
}
private int query(int[] bit, int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minimumAdjacentSwaps("abcde", "acb"));
}
}from collections import defaultdict, deque
class Solution:
def minimumAdjacentSwaps(self, original: str, corrupted: str) -> int:
# Map each character in original to a queue of its indices
char_indices = defaultdict(deque)
for i, c in enumerate(original):
char_indices[c].append(i)
# Get the target positions in original for each character in corrupted
target_positions = []
for c in corrupted:
target_positions.append(char_indices[c].popleft())
# Count the number of inversions in target_positions using a Fenwick Tree
n = len(target_positions)
bit = [0] * (n + 1)
def update(idx):
while idx <= n:
bit[idx] += 1
idx += idx & (-idx)
def query(idx):
s = 0
while idx > 0:
s += bit[idx]
idx -= idx & (-idx)
return s
inversions = 0
for i, pos in enumerate(target_positions):
inversions += i - query(pos)
update(pos)
return inversions
if __name__ == "__main__":
sol = Solution()
print(sol.minimumAdjacentSwaps("abcde", "acb"))/**
* @param {string} original
* @param {string} corrupted
* @return {number}
*/
var minimumAdjacentSwaps = function(original, corrupted) {
// Map each character in original to a queue of its indices
const charIndices = new Map();
for (let i = 0; i < original.length; i++) {
const c = original[i];
if (!charIndices.has(c)) {
charIndices.set(c, []);
}
charIndices.get(c).push(i);
}
// Get the target positions in original for each character in corrupted
const targetPositions = [];
for (const c of corrupted) {
const queue = charIndices.get(c);
targetPositions.push(queue.shift());
}
// Count the number of inversions in targetPositions using a Fenwick Tree
const n = targetPositions.length;
const bit = new Array(n + 1).fill(0);
const update = (idx) => {
while (idx <= n) {
bit[idx]++;
idx += idx & (-idx);
}
};
const query = (idx) => {
let sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
};
let inversions = 0;
for (let i = 0; i < n; i++) {
const pos = targetPositions[i];
inversions += i - query(pos);
update(pos);
}
return inversions;
};
console.log(minimumAdjacentSwaps("abcde", "acb"));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.