Given string str, the task is to find the minimum number of characters to be replaced to make a given string palindrome. Replacing a character means replacing it with any single character in the same position. We are not allowed to remove or add any characters.
If there are multiple answers, print the lexicographically smallest string.
Examples:
Input: str = "Lazyroar" Output: 2 Lazyroar 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 up to (length)/2-1 and check if a character at the i-th index i.e. s[i]!=s[length-i-1], then we will replace the alphabetically larger character with the one which is alphabetically smaller among them and continue the same process until all the elements get traversed.
Below is the implementation of the above approach:
C++
// C++ Implementation of the above approach#include<bits/stdc++.h>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<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] ; } printf("Minimum characters to be replaced = %d\n", (cc)) ; cout<<s<<endl;}// Driver codeint main(){string s = "Lazyroar";change((s));return 0;}//contributed by Arnab Kundu |
Java
// Java Implementation of the above approachimport java.util.*;class GFG{// Function to find the minimum number// character change requiredstatic 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 codepublic static void main(String args[]){ String s = "Lazyroar"; change((s));}}// This code is contributed by// Nikhil Gupta |
Python
# Python Implementation of the above approach# Function to find the minimum number# character change requiredimport math as madef 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]<s[n-i-1]): s[n-i-1]= s[i] else: s[i]= s[n-i-1] print("Minimum characters to be replaced = ", str(cc)) print(*s, sep ="") # Driver codes = "Lazyroar"change(list(s)) |
C#
// C# Implementation of the above approachusing System; class GFG{// Function to find the minimum number// character change requiredstatic 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 codepublic static void Main(String []args){ String s = "Lazyroar"; change((s));}}// This code contributed by Rajput-Ji |
PHP
<?php// PHP Implementation of the above approach// Function to find the minimum number// character change required function change($s){ // Finding the length of the string $n = strlen($s); // To store the number of replacement operations $cc = 0; for($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] ; } echo "Minimum characters to be replaced = ". $cc."\n" ; echo $s."\n";}// Driver code$s = "Lazyroar";change(($s));return 0;?> |
Javascript
<script>// 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 codevar s = "Lazyroar".split('');change((s));</script> |
Output:
Minimum characters to be replaced = 2 geeeg
