Solution For Minimum Number Of Moves To Make Palindrome

The problem statement is as follows:

Given a string s, return the minimum number of moves required to make s a palindrome. A move is defined as inserting a character at any position, deleting any character from any position, or replacing any character.

For example:
Input: “abcd”
Output: 3
Explanation: Insert ‘b’ and ‘c’ to make “bacd” then replace ‘a’ with ‘b’.

To solve this problem, we can use dynamic programming. We can create a 2D array dp where dp[i][j] represents the minimum number of moves required to make the substring s[i…j] a palindrome.

We can initialize the diagonal elements of the array to 0 because a single character string is already a palindrome. For all other elements dp[i][j], we can use the following recurrence relation based on the length of the substring:

if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] else:
dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1

Here, if the first and last characters of the substring are same, we do not need to make any additional moves. So, we can just look at the minimum moves required for the remaining substring by excluding the first and last characters i.e. dp[i+1][j-1]. If they are different, we have three options – we can either insert a character at the beginning (dp[i+1][j]), delete a character from the end (dp[i][j-1]), or replace the first or last character (dp[i+1][j-1]). We can choose the option that gives us the minimum number of moves and add 1 to it.

At the end, the value at dp[0][n-1] gives us the minimum number of moves required to make the whole string s a palindrome.

Here is the Python implementation of the solution:

def minMovesToPalindrome(s):
n = len(s)
dp = [[0] * n for _ in range(n)]

for gap in range(1, n):
    for i in range(n-gap):
        j = i + gap

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]
        else:
            dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1

return dp[0][n-1]

Example

s = “abcd”
print(minMovesToPalindrome(s)) # Output: 3

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

Step by Step Implementation For Minimum Number Of Moves To Make Palindrome

class Solution {
    public int minMoves(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
}

def minMoves(s): 

# Base case 

if s == s[::-1]: 

return 0

# Initialize result 

res = 0

# Consider each character as starting 

# point and find minimum number of 

# moves required to make it a palindrome 

for i in range(len(s)): 

# Find minimum moves required to 

# make str[i..len-1] a palindrome 

res += minMoves(s[i:]) 

return res

var minMoves = function(s) {
  // your code goes here
};

int minimumMoves(string s) {
    int n = s.length();
    int dp[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i - 1][j + 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j + 1]);
            }
        }
    }
    return dp[n - 1][0];
}

using System; 

public class Solution { 

// Function to find the minimum number of moves 
// required to make a string a palindrome 
public static int minMoves(string str) 
{ 

// Initialize left and right pointers 
int l = 0, r = str.Length - 1; 

// Initialize result 
int res = 0; 

// Iterate while l < r 
while (l < r) 
{ 
// If str[l] is not equal to str[r] 
// then find the smaller of str[l] 
// or str[r] and increment result by 
// this value 
if (str[l] != str[r]) 
{ 
res += Math.Min(str[l], str[r]); 
} 

// Increment l and decrement r 
l++; 
r--; 
} 

// required minimum moves 
return res; 
} 

// Driver code 
public static void Main() 
{ 
string str = "abcba"; 

Console.Write(minMoves(str)); 
} 
} 

// This code is contributed by Smitha Dinesh Semwal