Galactic Transmission Correction — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n log n)

SpaceO(n)

Problem Description

Given a transmission string S and a corrupted subsequence C (|C| ≤ |S|) consisting of characters that appear in S, determine the smallest number of adjacent‑swap operations required to reorder C so that its characters appear in the same relative order as they do in S. In one operation you may swap C[i] and C[i+1] for any valid i. It is guaranteed that C can be formed by selecting |C| characters from S in left‑to‑right order (i.e., each character of C matches a distinct occurrence in S). Return the minimum number of swaps as an integer.

DSA Pattern Breakdown

"Galactic Transmission Correction"

medium

WHY DOES IT MATTER?

This pattern is essential because it bridges the gap between sequence alignment and inversion counting, a fundamental concept in combinatorics and algorithm design. It appears in problems involving sorting, permutation analysis, and sequence transformation, making it a versatile tool for tackling a wide range of medium to hard problems.

OPTIMIZATION CHALLENGE

The key insight is to decouple the mapping of characters to positions from the inversion counting. By using a greedy mapping and then applying an O(n log n) inversion counter, you avoid the O(n^2) complexity of naive approaches. The Fenwick Tree is particularly effective because it allows efficient point updates and prefix sum queries.

REAL-WORLD CONNECTION

In distributed systems, this pattern is analogous to reordering a list of tasks or messages to match a desired execution order. For example, in a message queue system, you might need to reorder messages to ensure they are processed in a specific sequence, and the minimum number of swaps helps optimize the reordering process.

In interviews, clearly articulate the two-step process: mapping and inversion counting. Emphasize why the greedy mapping is correct and how the inversion count relates to adjacent swaps. Be prepared to explain the Fenwick Tree or Merge Sort approach in detail, as interviewers often probe the implementation details.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to counting the minimum number of adjacent swaps required to transform a sequence C into a sequence that is a subsequence of S, preserving the relative order of characters in S. This is fundamentally a problem of mapping the positions of characters in C to their corresponding positions in S and then counting the inversions in the resulting index sequence. If we map each character in C to the earliest available occurrence in S (greedily), we obtain a sequence of indices. The number of adjacent swaps needed to sort this index sequence in increasing order is exactly the number of inversions in the sequence. This is because each adjacent swap reduces the inversion count by exactly one, and the sorted sequence has zero inversions.

Naive approaches that simulate the swaps or use O(n^2) inversion counting (like nested loops) fail on large inputs where |S| and |C| can be up to 10^5 or 10^6. The optimal paradigm involves two key steps: first, efficiently mapping characters in C to positions in S using a greedy pointer or precomputed position lists, and second, counting inversions in O(n log n) time using a Fenwick Tree (Binary Indexed Tree) or a Merge Sort-based inversion counter. The Fenwick Tree approach is particularly efficient because it allows point updates and prefix sum queries in O(log n) time, making the total inversion count O(n log n).

The greedy mapping is critical: for each character in C, we must assign it to the earliest possible position in S that hasn't been used yet. This ensures that the relative order in S is preserved and minimizes the potential for unnecessary inversions. If we were to assign characters to arbitrary positions, we might create extra inversions that don't reflect the true minimum swaps. The correctness of the greedy approach follows from the fact that choosing an earlier position in S for a character in C cannot increase the number of inversions compared to choosing a later position, as it leaves more room for subsequent characters to be placed in increasing order.

Interview Questions on This Problem

Q1At a fintech platform, you're building a transaction reconciliation system where two ledgers have the same set of transactions but in different orders. How would you compute the minimum number of adjacent swaps needed to align one ledger to the other, assuming transactions are unique?

Map each transaction in the second ledger to its index in the first ledger, then count the inversions in the resulting index sequence using a Fenwick Tree or Merge Sort. The inversion count equals the minimum adjacent swaps. This is O(n log n) and handles large ledgers efficiently.

Q2In a high-growth startup's content delivery network, you need to reorder a list of cached assets to match the most popular access pattern. If the current order is C and the target order is a subsequence of the full asset list S, how do you minimize adjacent swaps to transform C into the target order?

Treat the target order as the desired subsequence of S. Map each asset in C to its position in S greedily, then count inversions in the mapped index sequence. The inversion count gives the minimum adjacent swaps. Use a Fenwick Tree for O(n log n) performance.

Q3At a global product company, you're optimizing a search ranking system where documents are reordered based on user feedback. If the current ranking is C and the ideal ranking is a subsequence of all documents S, how do you compute the minimum adjacent swaps to reach the ideal ranking?

Map each document in C to its position in S using a greedy approach (earliest available position), then count inversions in the resulting index sequence. The inversion count is the answer. Use a Merge Sort-based inversion counter or Fenwick Tree for efficiency.

Examples

Example 1

Input

S = "ABCDAB", C = "BACA"

Output

Explanation: Map each character of C to its earliest unused occurrence in S → positions [1,0,2,4]. The target order is [0,1,2,4]; one inversion (1,0) means one adjacent swap.

Example 2

Input

S = "GATACAG", C = "AGACA"

Output

Explanation: Corresponding indices are [1,0,3,4,5]; sorting gives [0,1,3,4,5]. Only the pair (1,0) is inverted, so one swap suffices.

Example 3

Input

S = "XYZXYZXYZ", C = "ZZYXXY"

Output

Explanation: Indices obtained: [2,5,0,1,4,3]. Counting inversions yields 7, which is the minimal number of adjacent swaps needed.

Constraints

1 <= |S| <= 2*10^5
1 <= |C| <= |S|
S and C contain only uppercase English letters
C is a subsequence of S (each character matches a distinct occurrence)

Optimal Approach & Strategy

Map each character in C to its earliest available position in S greedily, then count the inversions in the resulting index sequence using a Fenwick Tree or Merge Sort. This runs in O(n log n) time and is efficient for large inputs.

Brute Force Approach

Simulate the adjacent swaps by repeatedly finding the next character in C that should be moved and swapping it into place, counting each swap. This is O(n^2) or worse and is too slow for large inputs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

function minSwapsToReorder(S, C) {
    const n = S.length;
    const m = C.length;
    
    // Store indices of each character in S
    const charIndices = new Array(26).fill().map(() => []);
    for (let i = 0; i < n; ++i) {
        charIndices[S.charCodeAt(i) - 65].push(i);
    }
    
    // Map each character in C to its corresponding index in S
    const mappedIndices = new Array(m);
    for (let i = 0; i < m; ++i) {
        const charCode = C.charCodeAt(i) - 65;
        mappedIndices[i] = charIndices[charCode].shift();
    }
    
    // Count inversions using Fenwick Tree
    const maxIndex = n;
    const fenwick = new Array(maxIndex + 1).fill(0);
    
    const update = (idx) => {
        while (idx <= maxIndex) {
            fenwick[idx]++;
            idx += idx & (-idx);
        }
    };
    
    const query = (idx) => {
        let sum = 0;
        while (idx > 0) {
            sum += fenwick[idx];
            idx -= idx & (-idx);
        }
        return sum;
    };
    
    let inversions = 0;
    for (let i = 0; i < m; ++i) {
        const pos = mappedIndices[i] + 1; // 1-based index
        const countBefore = query(pos - 1);
        inversions += (i - countBefore);
        update(pos);
    }
    
    return inversions;
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [S, C] = lines[0].split(' ');
    console.log(minSwapsToReorder(S, C));
});

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int minSwapsToReorder(const string& S, const string& C) {
    int n = S.size();
    int m = C.size();
    
    // Store indices of each character in S
    vector<queue<int>> charIndices(26);
    for (int i = 0; i < n; ++i) {
        charIndices[S[i] - 'A'].push(i);
    }
    
    // Map each character in C to its corresponding index in S
    vector<int> mappedIndices(m);
    for (int i = 0; i < m; ++i) {
        int idx = charIndices[C[i] - 'A'].front();
        charIndices[C[i] - 'A'].pop();
        mappedIndices[i] = idx;
    }
    
    // Count inversions in mappedIndices
    // Use Fenwick Tree for efficient inversion counting
    int maxIndex = n;
    vector<int> fenwick(maxIndex + 1, 0);
    
    auto update = [&](int idx) {
        while (idx <= maxIndex) {
            fenwick[idx]++;
            idx += idx & (-idx);
        }
    };
    
    auto query = [&](int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += fenwick[idx];
            idx -= idx & (-idx);
        }
        return sum;
    };
    
    long long inversions = 0;
    for (int i = 0; i < m; ++i) {
        int pos = mappedIndices[i] + 1; // 1-based index
        // Count how many elements before i have index greater than mappedIndices[i]
        int countBefore = query(pos - 1);
        inversions += (i - countBefore);
        update(pos);
    }
    
    return (int)inversions;
}

int main() {
    string S, C;
    cin >> S >> C;
    cout << minSwapsToReorder(S, C) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int minSwapsToReorder(String S, String C) {
        int n = S.length();
        int m = C.length();
        
        // Store indices of each character in S
        Queue<Integer>[] charIndices = new Queue[26];
        for (int i = 0; i < 26; i++) {
            charIndices[i] = new LinkedList<>();
        }
        for (int i = 0; i < n; i++) {
            charIndices[S.charAt(i) - 'A'].offer(i);
        }
        
        // Map each character in C to its corresponding index in S
        int[] mappedIndices = new int[m];
        for (int i = 0; i < m; i++) {
            mappedIndices[i] = charIndices[C.charAt(i) - 'A'].poll();
        }
        
        // Count inversions using Fenwick Tree
        int maxIndex = n;
        int[] fenwick = new int[maxIndex + 1];
        
        for (int i = 0; i < m; i++) {
            int pos = mappedIndices[i] + 1; // 1-based index
            int countBefore = query(fenwick, pos - 1);
            int inversions = i - countBefore;
            update(fenwick, pos, maxIndex);
        }
        
        // Recalculate inversions properly
        int inversions = 0;
        Arrays.fill(fenwick, 0);
        for (int i = 0; i < m; i++) {
            int pos = mappedIndices[i] + 1;
            int countBefore = query(fenwick, pos - 1);
            inversions += (i - countBefore);
            update(fenwick, pos, maxIndex);
        }
        
        return inversions;
    }
    
    private static void update(int[] fenwick, int idx, int maxIndex) {
        while (idx <= maxIndex) {
            fenwick[idx]++;
            idx += idx & (-idx);
        }
    }
    
    private static int query(int[] fenwick, int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += fenwick[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        String C = scanner.next();
        System.out.println(minSwapsToReorder(S, C));
    }
}

def min_swaps_to_reorder(S: str, C: str) -> int:
    n = len(S)
    m = len(C)
    
    # Store indices of each character in S
    char_indices = {chr(ord('A') + i): [] for i in range(26)}
    for i, ch in enumerate(S):
        char_indices[ch].append(i)
    
    # Map each character in C to its corresponding index in S
    mapped_indices = []
    for ch in C:
        mapped_indices.append(char_indices[ch].pop(0))
    
    # Count inversions using Fenwick Tree
    max_index = n
    fenwick = [0] * (max_index + 1)
    
    def update(idx):
        while idx <= max_index:
            fenwick[idx] += 1
            idx += idx & (-idx)
    
    def query(idx):
        s = 0
        while idx > 0:
            s += fenwick[idx]
            idx -= idx & (-idx)
        return s
    
    inversions = 0
    for i, pos in enumerate(mapped_indices):
        pos_1based = pos + 1
        count_before = query(pos_1based - 1)
        inversions += (i - count_before)
        update(pos_1based)
    
    return inversions

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().split()
    S = input_data[0]
    C = input_data[1]
    print(min_swaps_to_reorder(S, C))

function minSwapsToReorder(S, C) {
    const n = S.length;
    const m = C.length;
    
    // Store indices of each character in S
    const charIndices = new Array(26).fill().map(() => []);
    for (let i = 0; i < n; ++i) {
        charIndices[S.charCodeAt(i) - 65].push(i);
    }
    
    // Map each character in C to its corresponding index in S
    const mappedIndices = new Array(m);
    for (let i = 0; i < m; ++i) {
        const charCode = C.charCodeAt(i) - 65;
        mappedIndices[i] = charIndices[charCode].shift();
    }
    
    // Count inversions using Fenwick Tree
    const maxIndex = n;
    const fenwick = new Array(maxIndex + 1).fill(0);
    
    const update = (idx) => {
        while (idx <= maxIndex) {
            fenwick[idx]++;
            idx += idx & (-idx);
        }
    };
    
    const query = (idx) => {
        let sum = 0;
        while (idx > 0) {
            sum += fenwick[idx];
            idx -= idx & (-idx);
        }
        return sum;
    };
    
    let inversions = 0;
    for (let i = 0; i < m; ++i) {
        const pos = mappedIndices[i] + 1; // 1-based index
        const countBefore = query(pos - 1);
        inversions += (i - countBefore);
        update(pos);
    }
    
    return inversions;
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [S, C] = lines[0].split(' ');
    console.log(minSwapsToReorder(S, C));
});

Asked in Top Tech Interviews

Infosys

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.

Galactic Transmission Correction Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galactic Transmission Correction — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor