LeetCode Problem 2193

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Greedy, Binary Indexed Tree

Solution

LeetCode 2193 - Minimum Number of Moves to Make Palindrome

Problem Understanding

This problem asks us to transform a given string into a palindrome using the minimum number of adjacent swaps.

A palindrome is a string that reads the same forward and backward. For example, "abba" and "racecar" are palindromes.

The only operation allowed is swapping two neighboring characters. Each adjacent swap counts as one move. Our goal is to determine the minimum number of such moves required to rearrange the string into any valid palindrome.

The input is a string s containing only lowercase English letters. The problem guarantees that the string can always be rearranged into a palindrome. This guarantee is important because not every string can form a palindrome. For example, "abc" cannot become a palindrome because more than one character has an odd frequency.

The constraint 1 <= s.length <= 2000 tells us several important things:

• The string is relatively small, but not tiny.
• An exponential or factorial brute-force solution is impossible.
• An O(n^2) solution is acceptable because 2000^2 = 4,000,000, which is manageable.
• We should avoid unnecessary cubic behavior.

There are several important edge cases:

• Strings that are already palindromes, such as "abba" or "racecar", should return 0.
• Strings with exactly one unmatched middle character, such as "mamad", require careful handling because the unmatched character eventually belongs in the center.
• Strings where matching characters are far apart may require many swaps.
• Very short strings such as length 1 always require 0 moves.

The key challenge is minimizing adjacent swaps while correctly pairing matching characters from both ends inward.

Approaches

Brute Force Approach

A brute-force solution would try all possible sequences of adjacent swaps until a palindrome is formed, then return the minimum number of swaps among all possibilities.

One possible implementation could use BFS over all reachable string states. Each state represents a string configuration, and each edge represents one adjacent swap.

This approach is theoretically correct because BFS guarantees the shortest path in an unweighted graph. The first palindrome reached would therefore use the minimum number of swaps.

However, this approach is completely impractical. A string of length n can have up to n! permutations, and each state generates many neighboring states through swaps. The search space grows explosively.

Even for moderate string lengths, this becomes computationally impossible.

Optimal Greedy Two-Pointer Approach

The key insight is that we can greedily construct the palindrome from the outside inward.

A palindrome requires matching characters at symmetric positions. Therefore:

• The leftmost character must eventually match some identical character on the right side.
• If we find the matching character, we can move it into place using adjacent swaps.
• The number of swaps required is exactly the distance it must travel.

We use two pointers:

• left starts at the beginning.
• right starts at the end.

For each left position:

1. Search from right backward to find a matching character.
2. If a match is found, bubble that character toward the right position using adjacent swaps.
3. If no match exists, then the character at left must be the unique middle character of the palindrome. We move it one step toward the center and try again later.

This greedy strategy works because:

• Pairing outer characters first is always optimal.
• Adjacent swaps have additive cost.
• Delaying a valid outer pairing never reduces the total number of swaps.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n!)	Explores all reachable permutations
Optimal Greedy Two Pointers	O(n²)	O(n)	Greedily matches characters from both ends

Algorithm Walkthrough

1. Convert the string into a mutable array of characters.

Strings are immutable in Python and Go, so using an array or slice makes swapping easier. 2. Initialize two pointers.

Set:

• left = 0
• right = n - 1

These pointers represent the current outer positions we want to match. 3. Search for a matching character.

Starting from right, move backward until finding a character equal to chars[left].

This identifies the best matching partner for the current left character. 4. Handle the unmatched middle character case.

If the search reaches left itself, no matching character exists on the right side.

This means the current character must become the center character of the palindrome.

Since it belongs in the middle, swap it one position to the right and increment the move count by one.

Do not move the pointers yet because this character is still not in its final position. 5. Move the matching character into place.

If a match is found at position matchIndex, repeatedly swap it with the next character until it reaches position right.

Each adjacent swap costs one move. 6. Lock the pair into place.

Once the matching character reaches position right, we have successfully formed one symmetric pair.

Increment left and decrement right. 7. Continue until the pointers meet.

When left >= right, the palindrome is complete. 8. Return the total move count.

Why it works

The algorithm maintains the invariant that every processed outer pair is already in its optimal final position.

At each step, we greedily pair the leftmost unmatched character with the nearest valid matching character from the right side. Any valid palindrome must eventually pair these characters somehow, and moving the chosen match directly into place minimizes the required adjacent swaps.

If no match exists, the character must be the unique center character, so gradually moving it inward is unavoidable.

Because each operation is locally optimal and never disrupts previously completed pairs, the total number of swaps is globally minimal.

Python Solution

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        chars = list(s)
        left = 0
        right = len(chars) - 1
        moves = 0

        while left < right:
            match_index = right

            while match_index > left and chars[match_index] != chars[left]:
                match_index -= 1

            if match_index == left:
                chars[left], chars[left + 1] = chars[left + 1], chars[left]
                moves += 1
            else:
                while match_index < right:
                    chars[match_index], chars[match_index + 1] = (
                        chars[match_index + 1],
                        chars[match_index],
                    )
                    moves += 1
                    match_index += 1

                left += 1
                right -= 1

        return moves

The implementation closely follows the greedy two-pointer strategy.

We first convert the string into a list of characters because lists support in-place swapping efficiently.

The left and right pointers track the current positions we want to match. For each iteration, we search backward from right to locate a matching character for chars[left].

If no matching character exists, then the current character must become the middle character of the palindrome. We move it one step toward the center by swapping it with its neighbor.

If a match exists, we repeatedly perform adjacent swaps to bubble the matching character into the correct right position. Each swap increments the move counter.

Once the pair is fixed, we move inward and repeat the process.

Eventually all pairs are formed, and the total move count is returned.

Go Solution

func minMovesToMakePalindrome(s string) int {
	chars := []byte(s)

	left := 0
	right := len(chars) - 1
	moves := 0

	for left < right {
		matchIndex := right

		for matchIndex > left && chars[matchIndex] != chars[left] {
			matchIndex--
		}

		if matchIndex == left {
			chars[left], chars[left+1] = chars[left+1], chars[left]
			moves++
		} else {
			for matchIndex < right {
				chars[matchIndex], chars[matchIndex+1] =
					chars[matchIndex+1], chars[matchIndex]

				moves++
				matchIndex++
			}

			left++
			right--
		}
	}

	return moves
}

The Go implementation is nearly identical to the Python version.

Instead of a Python list, we use a []byte slice because Go strings are immutable. Swapping bytes directly is efficient and natural for lowercase English letters.

Go does not require special handling for integer overflow here because the maximum number of swaps is well within the range of a standard integer.

The swapping logic and pointer movement remain exactly the same as in Python.

Worked Examples

Example 1

Input:

s = "aabb"

Initial state:

Step	String	Action	Moves
Start	aabb	Initial string	0

Iteration 1

• left = 0
• right = 3
• Need match for 'a'

Search backward:

• index 3 → 'b'
• index 2 → 'b'
• index 1 → 'a'

Found match at index 1.

Bubble it to index 3:

aabb -> abab
abab -> abba

Step	String	Action	Moves
1	abab	Swap positions 1 and 2	1
2	abba	Swap positions 2 and 3	2

Now:

• left = 1
• right = 2

Characters already match.

Final answer:

2

Example 2

Input:

s = "letelt"

Initial state:

Step	String	Action	Moves
Start	letelt	Initial string	0

Iteration 1

• left = 0
• right = 5
• Need match for 'l'

Search backward:

• index 5 → 't'
• index 4 → 'l'

Found match at index 4.

Bubble to the right:

letelt -> letetl

Step	String	Action	Moves
1	letetl	Swap positions 4 and 5	1

Pointers move inward.

Iteration 2

• left = 1
• right = 4
• Need match for 'e'

Search backward:

• index 4 → 't'
• index 3 → 'e'

Found match at index 3.

Bubble to the right:

letetl -> lettel

Step	String	Action	Moves
2	lettel	Swap positions 3 and 4	2

Now the remaining middle section is already valid.

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each character may require scanning and swapping across the string
Space	O(n)	Mutable character array storage

The outer loop runs at most n / 2 times. Inside each iteration, we may scan backward across much of the remaining string and also perform multiple adjacent swaps.

In the worst case, both operations together produce quadratic behavior.

The space complexity is linear because we store a mutable copy of the input string.

Test Cases

sol = Solution()

assert sol.minMovesToMakePalindrome("aabb") == 2  # basic even-length example
assert sol.minMovesToMakePalindrome("letelt") == 2  # example with multiple choices
assert sol.minMovesToMakePalindrome("abba") == 0  # already a palindrome
assert sol.minMovesToMakePalindrome("racecar") == 0  # odd-length palindrome
assert sol.minMovesToMakePalindrome("mamad") == 3  # classic middle-character case
assert sol.minMovesToMakePalindrome("ntiin") == 1  # single adjacent swap
assert sol.minMovesToMakePalindrome("a") == 0  # single character
assert sol.minMovesToMakePalindrome("aa") == 0  # identical pair
assert sol.minMovesToMakePalindrome("abcba") == 0  # odd palindrome already valid
assert sol.minMovesToMakePalindrome("aacbb") == 4  # requires several swaps
assert sol.minMovesToMakePalindrome("bbaa") == 2  # reverse pairing arrangement
assert sol.minMovesToMakePalindrome("abcdcba") == 0  # longer palindrome
assert sol.minMovesToMakePalindrome("dmaam") == 2  # odd-length rearrangement

Test	Why
"aabb"	Basic even-length transformation
"letelt"	Multiple valid palindrome targets
"abba"	Already a palindrome
"racecar"	Odd-length palindrome
"mamad"	Requires moving unmatched middle character
"ntiin"	Minimal single-swap case
"a"	Smallest valid input
"aa"	Simple matching pair
"abcba"	Odd palindrome with center character
"aacbb"	Multiple swaps across the string
"bbaa"	Reverse ordering
"abcdcba"	Larger palindrome already correct
"dmaam"	Nontrivial odd-length arrangement

Edge Cases

Single Character Strings

A string of length one is already a palindrome because it reads the same in both directions. Naive implementations may accidentally perform unnecessary operations or produce index errors when trying to search for matching characters.

This implementation handles the case naturally because the loop condition left < right is immediately false.

Unique Middle Character

Odd-length palindromes contain exactly one character with odd frequency. For example, in "mamad", the character 'd' must eventually occupy the center position.

This is a common source of bugs because a matching partner cannot be found for that character. The implementation detects this situation when the backward search reaches left itself. Instead of forcing a nonexistent pair, the algorithm swaps the character one step toward the center.

Already Palindromic Strings

Strings like "abba" or "racecar" should return zero moves.

Some incorrect greedy implementations continue performing unnecessary swaps even when pairs already match. This implementation avoids that problem because matching characters are immediately accepted without additional work, and the pointers simply move inward.