Interstellar Message Repair — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

Given two strings representing encoded messages from a distant planet, determine the minimum number of adjacent character swaps required to make the strings identical. Swaps can only involve characters in alternate positions (i.e., 1st with 2nd, 3rd with 4th, etc.) in either string. If the strings cannot be made identical by swapping only alternate characters, return -1.

DSA Pattern Breakdown

"Interstellar Message Repair"

medium

WHY DOES IT MATTER?

Recognizing the "pair‑wise independent swap" pattern lets you convert a seemingly global rearrangement problem into a series of constant‑time local checks, dramatically shrinking the search space and avoiding exponential blow‑up.

OPTIMIZATION CHALLENGE

The key insight is that each allowed swap only toggles the order inside a fixed two‑element window, so the minimal cost per window can be pre‑computed by enumerating the four possible swap combinations and picking the cheapest feasible one.

REAL-WORLD CONNECTION

Think of a distributed system where each node can only exchange messages with its immediate neighbor in a fixed ring. The overall system state can be reconciled by fixing each neighbor pair locally, without needing a global coordination protocol.

During an interview, first verify the parity constraints (even length or matching last character) and then iterate block‑by‑block; this linear scan is both easy to code and hard to mess up, showcasing clean problem decomposition.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to a per‑pair decision because swaps are only allowed between adjacent characters in fixed odd‑even blocks (1‑2, 3‑4, …). Within each block the two characters can either stay in their original order or be swapped, and each swap costs exactly one operation. Consequently the global transformation is a composition of independent local transformations: for every block we must decide whether to swap none, one, or both strings so that the resulting ordered pair matches. A naïve approach that tries all possible sequences of swaps across the whole string would explode exponentially (2^(n/2) possibilities), which is infeasible for large inputs. The optimal paradigm treats each block as a tiny state machine with four deterministic outcomes, evaluates them in O(1) time, and aggregates the minimal cost across all blocks, yielding an overall linear‑time solution.

Interview Questions on This Problem

Q1How would you modify the solution if swaps were allowed on any adjacent pair, not just alternate positions?

When any adjacent swap is allowed, the problem becomes checking whether the two strings are anagrams and then counting the minimum number of adjacent swaps to transform one into the other, which can be solved with a greedy bubble‑sort‑like approach in O(n^2) or with a Fenwick tree in O(n log n) by counting inversions.

Q2Why is it sufficient to consider each odd‑even block independently rather than exploring interactions between blocks?

Because swaps are confined to characters inside the same block; no operation can move a character across block boundaries. Therefore the state of one block never influences the feasibility or cost of another block, allowing a decomposition into independent subproblems.

Q3What edge case makes the answer -1 even if the strings have the same multiset of characters?

If the length is odd, the last unpaired character cannot be moved. If that character differs between the two strings, no sequence of allowed swaps can reconcile them, leading to an immediate -1.

Examples

Example 1

Input

swap("abc", "bac")

Output

Explanation: Step-by-step: Given two strings "abc" and "bac", we can swap the first and second characters in the first string and the second and third characters in the second string, giving output 1.

Example 2

Input

swap("abc", "xyz")

Output

-1

Explanation: Step-by-step: Given two strings "abc" and "xyz", we cannot make the strings identical by swapping only alternate characters, so we return -1.

Constraints

1 <= length of strings <= 100
All characters in the strings are unique digits from 0 to 9

Optimal Approach & Strategy

Process the strings pairwise; for each block enumerate the four swap configurations, pick the one with the smallest cost that makes the two blocks identical, and accumulate the cost. If no configuration works, return -1.

Brute Force Approach

Try every combination of swapping or not swapping each allowed adjacent pair in both strings, simulate the resulting strings, and keep the minimum number of swaps that yields equality. This exhaustive search is exponential in the number of pairs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var swap = function(s1, s2) {
    let n = s1.length;
    if (n % 2 !== 0) return -1;
    
    let arr1 = s1.split('');
    let arr2 = s2.split('');
    let swaps = 0;
    
    for (let i = 0; i < n; i += 2) {
        if (arr1[i] !== arr2[i]) {
            if (arr1[i] === arr2[i+1] && arr1[i+1] === arr2[i]) {
                swaps++;
                [arr1[i], arr1[i+1]] = [arr1[i+1], arr1[i]];
            } else {
                return -1;
            }
        }
    }
    return swaps;
};

class Solution {
public:
    int swap(string s1, string s2) {
        int n = s1.size();
        if (n % 2 != 0) return -1;
        
        vector<int> pos1(26, -1), pos2(26, -1);
        for (int i = 0; i < n; i++) {
            pos1[s1[i] - 'a'] = i;
            pos2[s2[i] - 'a'] = i;
        }
        
        int swaps = 0;
        for (int i = 0; i < n; i += 2) {
            if (s1[i] != s2[i]) {
                if (s1[i] == s2[i+1] && s1[i+1] == s2[i]) {
                    swaps++;
                    swap(s1[i], s1[i+1]);
                } else {
                    return -1;
                }
            }
        }
        return swaps;
    }
};

class Solution {
    public int swap(String s1, String s2) {
        int n = s1.length();
        if (n % 2 != 0) return -1;
        
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int swaps = 0;
        
        for (int i = 0; i < n; i += 2) {
            if (arr1[i] != arr2[i]) {
                if (arr1[i] == arr2[i+1] && arr1[i+1] == arr2[i]) {
                    swaps++;
                    char temp = arr1[i];
                    arr1[i] = arr1[i+1];
                    arr1[i+1] = temp;
                } else {
                    return -1;
                }
            }
        }
        return swaps;
    }
}

class Solution:
    def swap(self, s1: str, s2: str) -> int:
        n = len(s1)
        if n % 2 != 0:
            return -1
        
        arr1 = list(s1)
        arr2 = list(s2)
        swaps = 0
        
        for i in range(0, n, 2):
            if arr1[i] != arr2[i]:
                if arr1[i] == arr2[i+1] and arr1[i+1] == arr2[i]:
                    swaps += 1
                    arr1[i], arr1[i+1] = arr1[i+1], arr1[i]
                else:
                    return -1
        return swaps

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var swap = function(s1, s2) {
    let n = s1.length;
    if (n % 2 !== 0) return -1;
    
    let arr1 = s1.split('');
    let arr2 = s2.split('');
    let swaps = 0;
    
    for (let i = 0; i < n; i += 2) {
        if (arr1[i] !== arr2[i]) {
            if (arr1[i] === arr2[i+1] && arr1[i+1] === arr2[i]) {
                swaps++;
                [arr1[i], arr1[i+1]] = [arr1[i+1], arr1[i]];
            } else {
                return -1;
            }
        }
    }
    return swaps;
};

Asked in Top Tech Interviews

Uber

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.

Interstellar Message Repair Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Interstellar Message Repair — 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