# The minimum number of characters that must be replaced to form a given string Palindrome

Python Methods and Functions | String Variables

If there are multiple answers, print the lexicographically smallest line.

Examples :

```
Input:  str = "geeks"
Output:  2 geeks can be converted to geeeg to make it palindrome
by replacing minimum characters.
Input:  str = "ameba"
Output:  1 We can get "abeba" or "amema" with only 1 change.
Among those two, "abeba" is lexicographically smallest.
```

Approach: run a loop from 0 to (length) / 2-1 and check if the character is at the i-th index, i.e. s [i]! = S [length-i-1], then we will replace the alphabetically larger character with one that is alphabetically smaller among them and continue the same process until all the elements have passed.

Below is the implementation of the above approach.

## Python

```# Python Implementation of the above approach

# Function to find the minimum number
# character change required
import math as ma
def change(s):

# Finding the length of the string
n = len(s)

# To store the number of replacement operations
cc = 0

for i in range(n//2):

# If the characters at location
# i and n-i-1 are same then
# no change is required
if(s[i]== s[n-i-1]):
continue

# Counting one change operation
cc+= 1

# Changing the character with higher
# ascii value with lower ascii value
if(s[i]```

### Output:

```Minimum characters to be replaced =  2
geeeg
```

## C++

```// C++ Implementation of the above approach
#include
using namespace std;

// Function to find the minimum number
// character change required

void change(string s)
{

// Finding the length of the string
int n = s.length();

// To store the number of replacement operations
int cc = 0;

for(int i=0;i```

## Java

```// Java Implementation of the above approach
import java.util.*;

class GFG
{

// Function to find the minimum number
// character change required
static void change(String s)
{

// Finding the length of the string
int n = s.length();

// To store the number of replacement operations
int cc = 0;

for(int i = 0; i < n/2; i++)
{

// If the characters at location
// i and n-i-1 are same then
// no change is required
if(s.charAt(i) == s.charAt(n - i - 1))
continue;

// Counting one change operation
cc += 1;

// Changing the character with higher
// ascii value with lower ascii value
if(s.charAt(i) < s.charAt(n - i - 1))
s = s.replace(s.charAt(n - i - 1),s.charAt(i));
else
s = s.replace(s.charAt(n-1),s.charAt(n - i - 1));
}
System.out.println("Minimum characters to be replaced = "+(cc)) ;
System.out.println(s);
}

// Driver code
public static void main(String args[])
{
String s = "geeks";
change((s));

}
}
```

```
```

## C#

```// C# Implementation of the above approach
using System;

class GFG
{

// Function to find the minimum number
// character change required
static void change(String s)
{

// Finding the length of the string
int n = s.Length;

// To store the number of
//replacement operations
int cc = 0;

for(int i = 0; i < n / 2; i++)
{

// If the characters at location
// i and n-i-1 are same then
// no change is required
if(s[i] == s[n - i - 1])
continue;

// Counting one change operation
cc += 1;

// Changing the character with higher
// ascii value with lower ascii value
if(s[i] < s[n - i - 1])
s = s.Replace(s[n - i - 1], s[i]);
else
s = s.Replace(s[n], s[n - i - 1]);
}
Console.WriteLine("Minimum characters " +
"to be replaced = " + (cc));
Console.WriteLine(s);
}

// Driver code
public static void Main(String []args)
{
String s = "geeks";
change((s));
}
}

```

## Javascript

```

// Javascript Implementation of the above approach

// Function to find the minimum number
// character change required

function change(s)
{

// Finding the length of the string
var n = s.length;

// To store the number of replacement operations
var cc = 0;

for(var i=0;i<n/2;i++)
{

// If the characters at location
// i and n-i-1 are same then
// no change is required
if(s[i]== s[n-i-1])
continue;

// Counting one change operation
cc+= 1;

// Changing the character with higher
// ascii value with lower ascii value
if(s[i]<s[n-i-1])
s[n-i-1]= s[i] ;
else
s[i]= s[n-i-1] ;
}
document.write("Minimum characters to be replaced = " + (cc)+"<br>");
document.write(s.join('') + "<br>");
}

// Driver code
var s = "geeks".split('');
change((s));

```

## How do I find the minimum changes needed to turn a string into a palindrome?

For a given string, find the minimum number of characters you need to insert to convert it to a palindrome. Before we go any further, let's take a look at a few examples:

• ab: The required number of inserts is 1, i.e. bab
• aa: the number of required inserts is 0, i.e. aa
• abcd: 3 inserts required, i.e. dcbabcd
• abcda: The required number of inserts is 2, i.e. adcbcda, which is the same as the number of insertions in the bcd substring (Why?).
• abcde: 4 inserts required, i.e. edcbabcde

Let the input string be str _0_. The problem can be broken down into three parts:

1. 1. Find the minimum number of insertions in the str _1_ substring.
2. 2. Find the minimum number of insertions in the str _2_ substring.
3. 3. Find the minimum number of insertions in the str _3_ substring.

### Recursive solution

The minimum number of inserts into the string str _4_ can be specified as:

```minInsertions (str _10_
min (minInsertions (str _8_), minInsertions (str _11_)
```
```# A Naive recursive program to find minimum
# number insertions needed to make a string
# palindrome
import sys

# Recursive function to find minimum
# number of insertions
def findMinInsertions(str, l, h):

# Base Cases
if (l > h):
return sys.maxsize
if (l == h):
return 0
if (l == h - 1):
return 0 if(str[l] == str[h]) else 1

# Check if the first and last characters are
# same. On the basis of the comparison result,
# decide which subrpoblem(s) to call

if(str[l] == str[h]):
return findMinInsertions(str, l + 1, h - 1)
else:
return (min(findMinInsertions(str, l, h - 1),
findMinInsertions(str, l + 1, h)) + 1)

# Driver Code
if __name__ == "__main__":

str = "geeks"
print(findMinInsertions(str, 0, len(str) - 1))

# This code is contributed by ita_c ```