2193. Minimum Number of Moves to Make Palindrome LeetCode Solution

In this guide, you will get 2193. Minimum Number of Moves to Make Palindrome LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Moves to Make Palindrome problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Number of Moves to Make Palindrome solution in C++
4. Minimum Number of Moves to Make Palindrome solution in Java
5. Minimum Number of Moves to Make Palindrome solution in Python
6. Additional Resources

Problem Statement of Minimum Number of Moves to Make Palindrome

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.

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)

2193. Minimum Number of Moves to Make Palindrome LeetCode Solution in C++

class Solution {
 public:
  int minMovesToMakePalindrome(string s) {
    int ans = 0;

    while (s.length() > 1) {
      // Greedily match the last digit.
      const int i = s.find(s.back());
      if (i == s.length() - 1) {
        // s[i] is the middle letter.
        ans += i / 2;
      } else {
        s.erase(i, 1);
        ans += i;  // Swap the matched letter to the left.
      }
      s.pop_back();
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2193. Minimum Number of Moves to Make Palindrome LeetCode Solution in Java

class Solution {
  public int minMovesToMakePalindrome(String s) {
    int ans = 0;
    StringBuilder sb = new StringBuilder(s);

    while (sb.length() > 1) {
      // Greedily match the last digit.
      final int i = sb.indexOf(sb.substring(sb.length() - 1));
      if (i == sb.length() - 1) {
        // s[i] is the middle letter.
        ans += i / 2;
      } else {
        sb.deleteCharAt(i);
        ans += i; // Swap the matched letter to the left.
      }
      sb.deleteCharAt(sb.length() - 1);
    }

    return ans;
  }
}
// code provided by PROGIEZ

2193. Minimum Number of Moves to Make Palindrome LeetCode Solution in Python

class Solution:
  def minMovesToMakePalindrome(self, s: str) -> int:
    ans = 0
    chars = list(s)

    while len(chars) > 1:
      # Greedily match the last digit.
      i = chars.index(chars[-1])
      if i == len(chars) - 1:
        # s[i] is the middle letter.
        ans += i // 2
      else:
        chars.pop(i)
        ans += i  # Swap the matched letter to the left.
      chars.pop()

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.