Formatted question description: https://leetcode.ca/all/2193.html

2193. Minimum Number of Moves to Make Palindrome (Hard)

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 that the input will be generated such that s can always be converted to a palindrome.

 

Example 1:

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: "aabb" -> "abab" -> "abba".
- We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:

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 "letelt" -> "letetl" -> "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.

Companies:
Microsoft

Related Topics:
Two Pointers, String, Greedy, Binary Indexed Tree

Similar Questions:

Solution 1. Greedy

Intuition 1: Consider the first and last character in the final palindrome, if they are neither the first nor the last character in the initial string, you must waste some steps.

Assume the final palindrome is a......a and the initial string is x..a....a.y (x, y are not a.). ..a....a.. can be completed earlier than a......a. (How can we formally prove this?)

Intuition 2: For s = "a....b..a...b", it takes the same number of steps to get "ab.........ba" and "ba.........ab".

Proof: a ( x ) b ( y ) a ( z ) b (x, y, z are the number of characters inbetween). Getting ab...ba takes x + (z+1) steps, and getting ba...ab takes (x+1) + z steps. So they are the same.

// OJ: https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/

// Time: O(N^2)
// Space: O(1)
// Ref: https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/discuss/1822174/
class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int ans = 0;
        while (s.size()) {
            int i = s.find(s.back());
            if (i == s.size() - 1) ans += i / 2; // this character should be put at the middle.
            else ans += i, s.erase(i, 1);
            s.pop_back();
        }
        return ans;
    }
};

This solution is tricky because it removes the characters instead of really moving them.

Assume s = "bbcca".

Step 1. Move a 2 steps to the center

Step 2. Move c 2 steps.

Step 3. No move needed for b.

If we do the moving instead of removal, we need to do it in the reversed order.

Step 1. no move needed for b "bbcca"

Step 2. Move c 2 steps "bbcca" -> "bcbca" -> "cbbca"

Step 3. Move a 2 steps "cbbca" -> "cbbac" -> "cbabc"

TODO

SegmentTree/BIT solutions

All Problems

All Solutions