2193. Minimum Number of Moves to Make Palindrome

Description

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.

Solution

minimum-number-of-moves-to-make-palindrome.py

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        n = len(s)
        s = list(s)
        start, end = 0, n - 1
        res = 0

        while start < end:
            if s[start] == s[end]:
                start += 1
                end -= 1
            else:
                i = end - 1

                while i > start and s[start] != s[i]:
                    i -= 1

                if start == i:
                    s[start], s[start + 1] = s[start + 1], s[start]
                    res += 1
                else:
                    while i < end:
                        s[i], s[i + 1] = s[i + 1], s[i]
                        i += 1
                        res += 1

                    start += 1
                    end -= 1

        return res

minimum-number-of-moves-to-make-palindrome.cpp

// https://molchevskyi.medium.com/best-solutions-for-microsoft-interview-tasks-min-swaps-to-make-palindrome-e931689f8cae

class Solution {
public:
    int minMovesToMakePalindrome(string s) {
        int s_size = s.size();
        int result = 0;
        int start = 0, end = s_size - 1;

        while (end > start) {
            // if we found different chars
            if (s[start] != s[end]) {
                int i = end - 1; // make an additional iterator from the end

                // move toward the start until we found the same char
                while (i > start && s[i] != s[start]) { --i; }

                // if we scanned whole the string and found
                // no one the same char swap char on the 
                // start with adjacent char it needs for 
                // case when the first char is not on it's 
                // right place all other parts of the 
                // algorithm don't process a char on the start
                if (i == start) {
                    swap(s[start], s[start + 1]);
                    ++result;
                }
                // if the same character found swap all 
                // chars from i to the end
                else {
                    while (i < end) {
                        swap(s[i], s[i + 1]);
                        ++result;
                        ++i;
                    }
                    ++start; --end;
                }
            }
            // if s[start] == s[end] shrink the processing window
            else {
                ++start; --end;
            }
        }
        return result;
    }
};