Minimum cost to make the String palindrome using ASCII values
Given an input string S, the task is to make it a palindrome and calculate the minimum cost for making it a palindrome, where you are allowed to use any one of the following operations any number of times:
- For replacing the current character with another character the cost will be the absolute difference in ASCII (American Standard Code for Information Interchange) values of these two characters
- Replace βaβ with both characters and this will cost 10. If the input string is already palindrome then return -1.
Examples:
Input: S = βmoonβ
Output: 1
Explanation: We need to make βmβ = = βnβ then the input string will become palindrome. So, the cost will be the ASCII value of βnβ β ASCII value of βmβ i.e. 1.Input: S = βzoneβ
Output: 11
Explanation: We need to make βzβ == βeβ and the absolute difference between their ASCII values is 21. So we replace both characters with βaβ and it will cost 10 which is more efficient than 21 and for making βoβ == βnβ the cost will be 1. Total cost = 10 + 1 .
Approach: This can be solved with the following idea:
For every pair of characters choose whether their ASCII difference gives an optimized answer or replacing them with βaβ gives the optimized answer.
Below are the steps involved in the implementation of the code:
- Initialize a variable minCost = 0 for tracking the cost.
- Iterate over the input string using a for loop from 0 to n/2(n is the size of the input string) and for every single iteration do the below-mentioned checks.
- If the absolute difference of ASCII values is smaller than 10 then add it to minCost otherwise add 10 to minCost.
- After the for loop is executed then check whether minCost is greater than 0 or not. If yes then return minCost otherwise return -1.
Below is the implementation of the above-mentioned approach in C++:
C++
// C++ Implementation #include <bits/stdc++.h> using namespace std; // Function to find cost for making it // palindrome int findminCost(string s) { // Initializing variable for // calculating minimum cost int minCost = 0; int n = s.size(); for ( int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { // If difference of ascii is // greater than 10 then we // replace both character // with 'a' and add 10 to // minCost minCost += min(10, abs (s[i] - s[n - i - 1])); } } if (minCost > 0) return minCost; // Returning -1 if the string is // already palindrome return -1; } // Driver code int main() { string s = "moon" ; // Function call cout << findminCost(s); return 0; } |
Java
// C++ Implementation public class MinimumCostPalindrome { // Function to find cost for making it // palindrome static int findMinCost(String s) { // Initializing variable for // calculating minimum cost int minCost = 0 ; int n = s.length(); for ( int i = 0 ; i < n / 2 ; i++) { if (s.charAt(i) != s.charAt(n - i - 1 )) { // If difference of ASCII is // greater than 10 then we // replace both characters // with 'a' and add 10 to // minCost minCost += Math.min( 10 , Math.abs(s.charAt(i) - s.charAt(n - i - 1 ))); } } if (minCost > 0 ) return minCost; // Returning -1 if the string is // already palindrome return - 1 ; } // Driver code public static void main(String[] args) { String s = "moon" ; // Function call System.out.println(findMinCost(s)); } } // This code is contributed by codearcade |
Python
# Function to find cost for making it # palindrome def find_min_cost(s): # Initializing variable for # calculating minimum cost min_cost = 0 n = len (s) for i in range (n / / 2 ): if s[i] ! = s[n - i - 1 ]: # If difference of ASCII is # greater than 10, then we # replace both characters # with 'a' and add 10 to # min_cost min_cost + = min ( 10 , abs ( ord (s[i]) - ord (s[n - i - 1 ]))) if min_cost > 0 : return min_cost # Returning -1 if the string is # already a palindrome return - 1 # Driver code def main(): s = "moon" # Function call print (find_min_cost(s)) if __name__ = = "__main__" : main() |
C#
// C# code of the above approach using System; public class MinimumCostPalindrome { // Function to find cost for making it // palindrome static int FindMinCost( string s) { // Initializing variable for // calculating minimum cost int minCost = 0; int n = s.Length; for ( int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { // If difference of ASCII is // greater than 10 then we // replace both characters // with 'a' and add 10 to // minCost minCost += Math.Min(10, Math.Abs(s[i] - s[n - i - 1])); } } if (minCost > 0) return minCost; // Returning -1 if the string is // already palindrome return -1; } // Driver code public static void Main( string [] args) { string s = "moon" ; // Function call Console.WriteLine(FindMinCost(s)); } } // This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
// Nikunj Sonigara // Function to find cost for making it palindrome function findminCost(s) { // Initializing variable for calculating minimum cost let minCost = 0; const n = s.length; for (let i = 0; i < Math.floor(n / 2); i++) { if (s[i] !== s[n - i - 1]) { // If difference of ASCII is greater than 10, then we // replace both characters with 'a' and add 10 to minCost minCost += Math.min(10, Math.abs(s.charCodeAt(i) - s.charCodeAt(n - i - 1))); } } if (minCost > 0) { return minCost; } // Returning -1 if the string is already a palindrome return -1; } // Driver code const s = "moon" ; // Function call console.log(findminCost(s)); |
1
Time Complexity: O(N)
Auxiliary Space: O(1)