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

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));
 
}
}

PHP

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

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