Given a string S of length N and 2 integers X and Y, the task is to find the minimum cost of converting the string to a palindrome by performing the following operations any number of times in any order:
- Move the leftmost character to the rightmost end of the string at cost X. i.e S1S2…SN gets converted into S2S3…SNS1.
- Replace any character of the string with any lowercase letter at cost Y.
Examples:
Input: N = 5, S = “rrefa”, X = 1, Y = 2
Output: 3
Explanation: First pay Y = 2 amount and replace S5 (i.e. ‘a’) with ‘e’. Now the string becomes “rrefe”. Now pay X = 1 amount to rotate the string once. Now the string becomes “refer” which is a palindrome. The total cost to achieve the same is 2 + 1 = 3.Input: N = 8, S = “bcdfcgaa”, X = 1000000000, Y = 1000000000
Output: 4000000000
Approach: This can be solved by the following idea:
It does not matter whether we replace a character before or after we move it. So, we will perform all the operation 1s before operation 2s for the sake of simplicity. We will fix how many times we will perform operation 1. Note that after N rotations the string becomes equal to the initial string. So, N-1 rotations are sufficient to arrive at the answer. Then, for each of the first N/2 characters we will check whether it matches with (N – i + 1)th character
(say its palindromic pair). If not, we have to pay cost Y to change any one of them.
The following steps can be used to solve the problem :
- Initialize a variable (say answer) to store the final answer.
- Iterate from i = 0 to N – 1, i.e. fix the number of rotations of the string (operation 1).
- Initialize a variable (say count) by 0 to store the number of operations 2 to be performed.
- Iterate from j = 0 to N – 1 (in the nested loop) to check how many characters of the string are not equal to their palindromic pair.
- If any character is not equal to its palindromic pair, increment the count.
- Calculate the cost of converting the string into palindrome for the current ‘i’.
- The minimum of all costs for each iteration would be the final answer.
Following is the code based on the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;#define int long long// Function to find minimum cost to convert// the given string into palindrome by// performing the given operationsint minCost(string S, int N, int X, int Y){ // Initializing a variable to store // the final answer int answer = 1e16; // Iterating from i=0 to N-1, i.e. // fixing the rotations of the // string (operation 1) for (int i = 0; i < N; i++) { // Variable to store the number // of operations 2 to be performed int count = 0; // Iterating from j=0 to N-1 to // check how many characters of // the string are not equal to // their palindromic pair for (int j = 0; j < N; j++) { // If any character of the // string is not equal to its // palindromic pair, // increment count if (S[(j + i) % N] != S[(N - 1 - j + i) % N]) { count++; } } // Cost to convert the string S to // palindrome when 'i' rotations // are performed int cost = X * i + Y * (count / 2); // Minimum of all these costs would // be the final answer answer = min(answer, cost); } // Returning answer return answer;}// Driver codeint32_t main(){ int N = 5, X = 1, Y = 2; string S = "rrefa"; // Function call int answer = minCost(S, N, X, Y); cout << answer; return 0;} |
Java
import java.util.*;public class Main { static long minCost(String S, int N, long X, long Y) { // Initializing a variable to store // the final answer long answer = Long.MAX_VALUE; // Iterating from i=0 to N-1, i.e. // fixing the rotations of the // string (operation 1) for (int i = 0; i < N; i++) { // Variable to store the number // of operations 2 to be performed int count = 0; // Iterating from j=0 to N-1 to // check how many characters of // the string are not equal to // their palindromic pair for (int j = 0; j < N; j++) { // If any character of the // string is not equal to its // palindromic pair, // increment count if (S.charAt((j + i) % N) != S.charAt((N - 1 - j + i) % N)) { count++; } } // Cost to convert the string S to // palindrome when 'i' rotations // are performed long cost = X * i + Y * (count / 2); // Minimum of all these costs would // be the final answer answer = Math.min(answer, cost); } // Returning answer return answer; } // Driver code public static void main(String[] args) { int N = 5; long X = 1, Y = 2; String S = "rrefa"; // Function call long answer = minCost(S, N, X, Y); System.out.println(answer); }} |
Python3
# Python code implementation:def minCost(S, N, X, Y): # Initializing a variable to store # the final answer answer = float('inf') # Iterating from i=0 to N-1, i.e. # fixing the rotations of the # string (operation 1) for i in range(N): # Variable to store the number # of operations 2 to be performed count = 0 # Iterating from j=0 to N-1 to # check how many characters of # the string are not equal to # their palindromic pair for j in range(N): # If any character of the # string is not equal to its # palindromic pair, # increment count if S[(j + i) % N] != S[(N - 1 - j + i) % N]: count += 1 # Cost to convert the string S to # palindrome when 'i' rotations # are performed cost = X * i + Y * (count // 2) # Minimum of all these costs would # be the final answer answer = min(answer, cost) # Returning answer return answer# Driver codeN = 5X = 1Y = 2S = "rrefa"# Function callanswer = minCost(S, N, X, Y)print(answer)# This code is contributed by sankar. |
C#
// C# code implemetationusing System;public class GFG { static long minCost(string S, int N, long X, long Y) { // Initializing a variable to store the final answer long answer = long.MaxValue; // Iterating from i=0 to N-1, i.e. fixing the // rotations of the string (operation 1) for (int i = 0; i < N; i++) { // Variable to store the number of operations 2 // to be performed int count = 0; // Iterating from j=0 to N-1 to check how many // characters of the string are not equal to // their palindromic pair for (int j = 0; j < N; j++) { // If any character of the string is not // equal to its palindromic pair, increment // count if (S[(j + i) % N] != S[(N - 1 - j + i) % N]) { count++; } } // Cost to convert the string S to palindrome // when 'i' rotations are performed long cost = X * i + Y * (count / 2); // Minimum of all these costs would be the final // answer answer = Math.Min(answer, cost); } // Returning answer return answer; } static public void Main() { // Code int N = 5; long X = 1, Y = 2; string S = "rrefa"; // Function call long answer = minCost(S, N, X, Y); Console.WriteLine(answer); }}// This code is contributed by karthik |
Javascript
// Javascript code for the above approachfunction minCost(S, N, X, Y) { // Initializing a variable to store // the final answer let answer = 1e16; // Iterating from i=0 to N-1, i.e. // fixing the rotations of the // string (operation 1) for (let i = 0; i < N; i++) { // Variable to store the number // of operations 2 to be performed let count = 0; // Iterating from j=0 to N-1 to // check how many characters of // the string are not equal to // their palindromic pair for (let j = 0; j < N; j++) { // If any character of the // string is not equal to its // palindromic pair, // increment count if (S[(j + i) % N] !== S[(N - 1 - j + i) % N]) { count++; } } // Cost to convert the string S to // palindrome when 'i' rotations // are performed let cost = X * i + Y * Math.floor(count / 2); // Minimum of all these costs would // be the final answer answer = Math.min(answer, cost); } // Returning answer return answer;}// Driver codelet N = 5, X = 1, Y = 2;let S = "rrefa";// Function calllet answer = minCost(S, N, X, Y);console.log(answer);// This code is contributed by Prajwal Kandekar |
Output
3
Time Complexity: O(N*N)
Auxiliary Space: O(1)
New Approach:- Here Another approach to solve this problem is to use dynamic programming. We can define a state dp[i][j] as the minimum cost required to make the substring from i to j a palindrome. We can then use this state to compute the minimum cost required to make the entire string a palindrome.
We can start by initializing all the diagonal elements of the dp matrix to 0, as the minimum cost required to make a single character a palindrome is 0. We can then iterate over all possible substrings of length 2 to N, and compute the minimum cost required to make each substring a palindrome. We can do this by checking if the first and last characters of the substring match, and then adding the cost of either inserting a character or deleting a character based on which operation gives the minimum cost.
The final answer would be the value of dp[0][N-1], which represents the minimum cost required to make the entire string a palindrome.
|
Algorithm:-
|
Following is the code based on the above approach:-
C++
#include <algorithm>#include <cstring>#include <iostream>using namespace std;int minCost(string S, int N, int X, int Y){ // Initializing a 2D array to store the // minimum cost required to make a // substring from i to j a palindrome int dp[N][N]; // Filling the diagonal elements of the // dp matrix with 0, as the minimum cost // required to make a single character // a palindrome is 0 for (int i = 0; i < N; i++) { dp[i][i] = 0; } // Iterating over all possible substrings // of length 2 to N, and computing the // minimum cost required to make each // substring a palindrome for (int L = 2; L <= N; L++) { for (int i = 0; i < N - L + 1; i++) { int j = i + L - 1; if (S[i] == S[j]) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = min( min(dp[i][j - 1] + X, dp[i + 1][j] + X), dp[i + 1][j - 1] + Y); } } } // Returning the minimum cost required // to make the entire string a palindrome return dp[0][N - 1];}// Driver Codeint main(){ int N = 5; int X = 1; int Y = 2; string S = "rrefa"; // Function call int answer = minCost(S, N, X, Y); cout << answer << endl; return 0;} |
Java
public class Main { public static int minCost(String S, int N, int X, int Y) { // Initializing a 2D array to store the // minimum cost required to make a // substring from i to j a palindrome int[][] dp = new int[N][N]; // Filling the diagonal elements of the // dp matrix with 0, as the minimum cost // required to make a single character // a palindrome is 0 for (int i = 0; i < N; i++) { dp[i][i] = 0; } // Iterating over all possible substrings // of length 2 to N, and computing the // minimum cost required to make each // substring a palindrome for (int L = 2; L <= N; L++) { for (int i = 0; i < N - L + 1; i++) { int j = i + L - 1; if (S.charAt(i) == S.charAt(j)) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = Math.min( Math.min(dp[i][j - 1] + X, dp[i + 1][j] + X), dp[i + 1][j - 1] + Y); } } } // Returning the minimum cost required // to make the entire string a palindrome return dp[0][N - 1]; } // Driver Code public static void main(String[] args) { int N = 5; int X = 1; int Y = 2; String S = "rrefa"; // Function call int answer = minCost(S, N, X, Y); System.out.println(answer); }} |
Python
def minCost(S, N, X, Y): # Initializing a 2D array to store the # minimum cost required to make a # substring from i to j a palindrome dp = [[0 for i in range(N)] for j in range(N)] # Filling the diagonal elements of the # dp matrix with 0, as the minimum cost # required to make a single character # a palindrome is 0 for i in range(N): dp[i][i] = 0 # Iterating over all possible substrings # of length 2 to N, and computing the # minimum cost required to make each # substring a palindrome for L in range(2, N+1): for i in range(N-L+1): j = i + L - 1 if S[i] == S[j]: dp[i][j] = dp[i+1][j-1] else: dp[i][j] = min(dp[i][j-1]+X, dp[i+1][j]+X, dp[i+1][j-1]+Y) # Returning the minimum cost required # to make the entire string a palindrome return dp[0][N-1]# Driver codeN = 5X = 1Y = 2S = "rrefa"# Function callanswer = minCost(S, N, X, Y)print(answer) |
C#
using System;class Program{ static int MinCost(string S, int N, int X, int Y) { // Initializing a 2D array to store the // minimum cost required to make a // substring from i to j a palindrome int[,] dp = new int[N, N]; // Filling the diagonal elements of the // dp matrix with 0, as the minimum cost // required to make a single character // a palindrome is 0 for (int i = 0; i < N; i++) { dp[i, i] = 0; } // Iterating over all possible substrings // of length 2 to N, and computing the // minimum cost required to make each // substring a palindrome for (int L = 2; L <= N; L++) { for (int i = 0; i < N - L + 1; i++) { int j = i + L - 1; if (S[i] == S[j]) { dp[i, j] = dp[i + 1, j - 1]; } else { dp[i, j] = Math.Min(Math.Min(dp[i, j - 1] + X, dp[i + 1, j] + X), dp[i + 1, j - 1] + Y); } } } // Returning the minimum cost required // to make the entire string a palindrome return dp[0, N - 1]; } static void Main(string[] args) { int N = 5; int X = 1; int Y = 2; string S = "rrefa"; // Function call int answer = MinCost(S, N, X, Y); Console.WriteLine(answer); }} |
Javascript
function minCost(S, N, X, Y){ // Initializing a 2D array to store the // minimum cost required to make a // substring from i to j a palindrome const dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(N).fill(0); } // Filling the diagonal elements of the // dp matrix with 0, as the minimum cost // required to make a single character // a palindrome is 0 for (let i = 0; i < N; i++) { dp[i][i] = 0; } // Iterating over all possible substrings // of length 2 to N, and computing the // minimum cost required to make each // substring a palindrome for (let L = 2; L <= N; L++) { for (let i = 0; i <= N - L; i++) { const j = i + L - 1; if (S[i] === S[j]) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = Math.min(dp[i][j - 1] + X, dp[i + 1][j] + X, dp[i + 1][j - 1] + Y); } } } // Returning the minimum cost required // to make the entire string a palindrome return dp[0][N - 1];}// Driver codeconst N = 5;const X = 1;const Y = 2;const S = "rrefa";// Function callconst answer = minCost(S, N, X, Y);console.log(answer); |
Output
3
Time Complexity:- The time complexity of the given code is O(N^2) because there are two nested loops, where the outer loop iterates N-1 times and the inner loop iterates N-L+1 times (where L ranges from 2 to N). Each iteration of the inner loop takes constant time, so the total time complexity is O((N-1) * (N-1)) = O(N^2).
Space Complexity:- The space complexity of the given code is also O(N^2) because it uses a 2D array (dp) of size NxN to store the minimum cost required to make each substring a palindrome.
