Show problems as
Classic problem #2193HardTwo PointersStringGreedyBinary Indexed Tree

Minimum Number of Moves to Make Palindrome

Real-world version: Swapping Neighbours Until the Strip Reads Alike Both Ways
Tracked in this browser only
Read Minimum Number of Moves to Make Palindrome on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_moves_to_make_palindrome(strip: str) -> int:
Java
public int minMovesToMakePalindrome(String strip)

More on the same topics