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 theminimum number of moves needed to make s a palindrome.

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

Examples

Example 1

1
2
3
4
5
6
7

Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "a _**ab**_ b" -> "ab _**ab**_ " -> "abba".
- We can obtain "baab" from s in 2 moves: "a _**ab**_ b" -> "_**ab**_ ab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2

1
2
3
4
5
6
7

Input: s = "letelt"
Output: 2
Explanation:
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "lete _**lt**_ " -> "let _**et**_ l" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

Constraints

  • 1 <= s.length <= 2000
  • s consists only of lowercase English letters.
  • s can be converted to a palindrome using a finite number of moves.

Solution

Method 1 – Greedy Two-Pointer Swaps

Intuition

To make a palindrome, match characters from both ends. If the left and right match, move inward. If not, find the matching character for the left (or right) and swap it adjacent until it reaches the correct position, counting moves. If a character is unique (odd count), it must be in the center.

Approach

  1. Use two pointers (left, right).
  2. If s[left] == s[right], move both inward.
  3. Else, search for a matching character for s[left] from right-1 to left+1. If found, swap it rightward, counting moves. If not found, swap s[left] to the center, counting moves.
  4. Repeat until pointers meet.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <string>
using namespace std;
class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int ans = 0, l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] == s[r]) {
                ++l; --r;
            } else {
                int k = r;
                while (k > l && s[k] != s[l]) --k;
                if (k == l) {
                    swap(s[l], s[l+1]);
                    ++ans;
                } else {
                    for (int i = k; i < r; ++i) {
                        swap(s[i], s[i+1]);
                        ++ans;
                    }
                    ++l; --r;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func minMovesToMakePalindrome(s string) int {
    arr := []byte(s)
    ans, l, r := 0, 0, len(arr)-1
    for l < r {
        if arr[l] == arr[r] {
            l++; r--
        } else {
            k := r
            for k > l && arr[k] != arr[l] { k-- }
            if k == l {
                arr[l], arr[l+1] = arr[l+1], arr[l]
                ans++
            } else {
                for i := k; i < r; i++ {
                    arr[i], arr[i+1] = arr[i+1], arr[i]
                    ans++
                }
                l++; r--
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int minMovesToMakePalindrome(String s) {
        char[] arr = s.toCharArray();
        int ans = 0, l = 0, r = arr.length - 1;
        while (l < r) {
            if (arr[l] == arr[r]) {
                l++; r--;
            } else {
                int k = r;
                while (k > l && arr[k] != arr[l]) k--;
                if (k == l) {
                    char tmp = arr[l]; arr[l] = arr[l+1]; arr[l+1] = tmp;
                    ans++;
                } else {
                    for (int i = k; i < r; ++i) {
                        char tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp;
                        ans++;
                    }
                    l++; r--;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun minMovesToMakePalindrome(s: String): Int {
        val arr = s.toCharArray()
        var ans = 0; var l = 0; var r = arr.size - 1
        while (l < r) {
            if (arr[l] == arr[r]) {
                l++; r--
            } else {
                var k = r
                while (k > l && arr[k] != arr[l]) k--
                if (k == l) {
                    arr[l] = arr[l+1].also { arr[l+1] = arr[l] }
                    ans++
                } else {
                    for (i in k until r) {
                        arr[i] = arr[i+1].also { arr[i+1] = arr[i] }
                        ans++
                    }
                    l++; r--
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        arr = list(s)
        ans, l, r = 0, 0, len(arr) - 1
        while l < r:
            if arr[l] == arr[r]:
                l += 1; r -= 1
            else:
                k = r
                while k > l and arr[k] != arr[l]:
                    k -= 1
                if k == l:
                    arr[l], arr[l+1] = arr[l+1], arr[l]
                    ans += 1
                else:
                    for i in range(k, r):
                        arr[i], arr[i+1] = arr[i+1], arr[i]
                        ans += 1
                    l += 1; r -= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn min_moves_to_make_palindrome(s: String) -> i32 {
        let mut arr: Vec<char> = s.chars().collect();
        let mut ans = 0;
        let (mut l, mut r) = (0, arr.len() - 1);
        while l < r {
            if arr[l] == arr[r] {
                l += 1; r -= 1;
            } else {
                let mut k = r;
                while k > l && arr[k] != arr[l] { k -= 1; }
                if k == l {
                    arr.swap(l, l+1);
                    ans += 1;
                } else {
                    for i in k..r {
                        arr.swap(i, i+1);
                        ans += 1;
                    }
                    l += 1; r -= 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    minMovesToMakePalindrome(s: string): number {
        const arr = s.split("");
        let ans = 0, l = 0, r = arr.length - 1;
        while (l < r) {
            if (arr[l] === arr[r]) {
                l++; r--;
            } else {
                let k = r;
                while (k > l && arr[k] !== arr[l]) k--;
                if (k === l) {
                    [arr[l], arr[l+1]] = [arr[l+1], arr[l]];
                    ans++;
                } else {
                    for (let i = k; i < r; ++i) {
                        [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
                        ans++;
                    }
                    l++; r--;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — n = length of s, for swaps.
  • 🧺 Space complexity: O(n) — for array copy.