Minimum Number of Moves to Make Palindrome

Minimum Number of Moves to Make Palindrome - Problem

You are given a string s consisting only of lowercase English letters.

In one move, you can select any two adjacent characters of s and swap them.

Return the minimum number of moves needed to make s a palindrome.

Note: The input will be generated such that s can always be converted to a palindrome.

Input & Output

Example 1 — Basic Case

$ Input: s = "aab"

› Output: 1

💡 Note: We can swap the second 'a' with 'b' to get 'aba', which is a palindrome. Only 1 adjacent swap is needed.

Example 2 — Already Palindrome

$ Input: s = "aba"

› Output: 0

💡 Note: The string is already a palindrome, so no moves are needed.

Example 3 — Multiple Swaps

$ Input: s = "letelt"

› Output: 2

💡 Note: We need 2 swaps to transform 'letelt' to a palindrome like 'tleelt'. Match 'l' at ends first, then match 'e' at next positions.

Constraints

1 ≤ s.length ≤ 2000
s consists only of lowercase English letters
s can be rearranged to form a palindrome

Visualization

Tap to expand

Understanding the Visualization

Input

String 'aab' that needs to become palindrome

Process

Use adjacent swaps to rearrange characters

Output

Minimum number of swaps needed: 1

Key Takeaway

🎯 Key Insight: Use greedy two-pointer approach to match characters from ends, bubbling nearest matches with adjacent swaps

Asked in

G Google 28 f Facebook 15 a Amazon 12

The key insight is to use a greedy two-pointer approach, matching characters from the ends toward the center. For each position, find the nearest matching character and bubble it using adjacent swaps. Best approach is Two Pointers with Greedy Matching. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Greedy with Character Counting	O(n²)	O(1)	Count character frequencies and greedily assign positions to minimize swaps
Two Pointers with Greedy Matching	O(n²)	O(1)	Use two pointers from ends, greedily match characters with minimum swaps
Brute Force Simulation	O(n!)	O(n)	Try all possible sequences of adjacent swaps until palindrome is achieved

Optimized Greedy with Character Counting — Algorithm Steps

Count frequency of each character
Determine palindrome structure (pairs + optional middle)
Greedily assign characters to positions minimizing swaps
Calculate total swap cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Pre-count all characters: a:2, b:1

Plan Structure

Determine pairs and middle character

Greedy Assignment

Assign characters to minimize total swaps

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int moves = 0;
    
    // Count character frequencies (assuming only lowercase letters)
    int freq[26] = {0};
    for (int i = 0; i < n; i++) {
        freq[s[i] - 'a']++;
    }
    
    int left = 0;
    int right = n - 1;
    
    while (left < right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        } else {
            // Find the closest matching character to s[left] from the right side
            int k = right - 1;
            while (k > left && s[k] != s[left]) {
                k--;
            }
            
            // Bubble the matching character to the right position
            while (k < right) {
                char temp = s[k];
                s[k] = s[k + 1];
                s[k + 1] = temp;
                moves++;
                k++;
            }
            
            left++;
            right--;
        }
    }
    
    return moves;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Character counting is O(n), but greedy assignment still requires O(n²) swaps in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Character frequency array has constant size (26 letters), plus constant extra variables

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Greedy with Character Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler