1021HardTwo PointersStringGreedyBinary Indexed Tree

Swapping Neighbours Until the Strip Reads Alike Both Ways

Tracked in this browser only

Trains the technique from

LeetCode 2193Minimum Number of Moves to Make Palindrome

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A strip of lowercase letters reads strip. One move swaps two letters standing next to each other.

Return the fewest moves that leave the strip reading the same backwards as forwards. The strip is always one that some number of moves can settle.

Examples

Example 1

Input: strip = "mamad"
Output: 3

The leading `m` needs the other `m` at the far end, and that one sits two places short of it, so two swaps carry it there. What is left inside reads `aad`, whose leading `a` needs one swap to bring the other `a` to its end, leaving the `d` in the middle. Three moves in all, ending at `madam`.

Example 2

Input: strip = "abba"
Output: 0

The strip already reads the same both ways, so nothing needs moving.

Example 3

Input: strip = "baa"
Output: 1

The `b` has no second copy, so it is the odd letter out and belongs in the middle. One swap with the `a` beside it gives `aba`.

Constraints

1 <= strip.length <= 2000
The strip is made of lowercase English letters.
Some number of moves can make the strip read the same both ways.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_moves_to_make_palindrome(strip: str) -> int:

Java

public int minMovesToMakePalindrome(String strip)

The intended approach

Time O(n^2) over the strip's length.Space O(n) for the working list.

Work from the outside inwards. Take the leftmost letter still in play; whatever ends up beside it at the far end has to be the same letter. Find the rightmost copy of it and walk that copy to the end with neighbour swaps, one move per step. Both ends are then settled, and the same question is left for the letters between them. Two observations make that greedy correct. Choosing the rightmost copy costs no more than any other copy would, since every other copy sits further from the end. And fixing the leftmost letter's partner never blocks a cheaper arrangement later, because if two chosen pairs had crossing spans, untangling them costs no extra moves at all. One case stands apart: when the leftmost letter has no other copy, it is the strip's odd letter out and belongs in the middle rather than at an end. Nudging it one place inward costs a single move, leaves everything else where it was, and lets the same reasoning carry on. Keeping the letters in a list and cutting out the two settled ends each round makes a round cost the remaining length, so the whole thing costs the length squared, which is comfortable at two thousand letters. Which end you settle first makes no difference. Reading the strip backwards is the same problem, and the same greedy run from the right returns the same count, so a solution built the other way round is equally correct.

Pythonentry point: min_moves_to_make_palindrome

def min_moves_to_make_palindrome(strip):
    letters = list(strip)
    moves = 0
    while len(letters) > 1:
        target = letters[0]
        at = len(letters) - 1
        while letters[at] != target:
            at -= 1
        if at == 0:
            letters[0], letters[1] = letters[1], letters[0]
            moves += 1
            continue
        moves += len(letters) - 1 - at
        letters.pop(at)
        letters.pop(0)
    return moves

The obvious version

Go the other way about it. List every arrangement of the letters that reads the same both ways, by permuting one half and mirroring it around any odd letter out. For each such arrangement, work out the fewest neighbour swaps that turn the strip into it: pair equal letters off left to right and count how many pairs of positions come out in the wrong order, which is exactly the number of swaps needed. Take the smallest count over all the arrangements. Costs the arrangements times the strip's length squared, rather than one pass from the outside in.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_moves_to_make_palindrome(strip):
    from itertools import permutations
    n = len(strip)
    tally = {}
    for ch in strip:
        tally[ch] = tally.get(ch, 0) + 1
    middle = ''
    half = []
    for ch in sorted(tally):
        if tally[ch] % 2:
            middle = ch
        half.extend([ch] * (tally[ch] // 2))
    best = None
    for order in set(permutations(half)):
        target = list(order)
        if middle:
            target.append(middle)
        target.extend(reversed(order))
        spots = {}
        for at, ch in enumerate(target):
            spots.setdefault(ch, []).append(at)
        used = {}
        mapped = []
        for ch in strip:
            k = used.get(ch, 0)
            used[ch] = k + 1
            mapped.append(spots[ch][k])
        swaps = 0
        for i in range(n):
            for j in range(i + 1, n):
                if mapped[i] > mapped[j]:
                    swaps += 1
        if best is None or swaps < best:
            best = swaps
    return best if best is not None else 0

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in