Minimize the String Transformation Cost
Given a string Str and cost array C[] of size n replacing Str[i] with any character will have cost C[i]. The task is to minimize the cost where every odd i, for all i from 1 to n have to match either,
- S[i] = S[n-i+1] and S[i+1] = S[n-i] or,
- S[i] = S[n-i] and S[i+1] = S[n-i+1]
Examples:
Input: N = 4, Str = bdbd, C[] = {1, 2, 3, 4}
Output: 0
Explanation: Given string is already 2-drome as all elements of it satisfy the second condition.Input: N = 8, Str = abbacaaa, C[] = {1, 2, 3, 4, 2, 3, 0, 1}
Output: 2
Explanation: Replacing the 5th character in string Str with b and the 7th character with b will be optimal
Approach: This can be solved with the following idea:
Start iterating from starting and last position as i and j. Check for each option given, if any option matched continue, or if not matched go for cost but select minimum from the options given.
Below are the steps involved:
- Iterate from starting as i and from last as j.
- if given option got matched, Continue the process
- Otherwise, go for:
- firstCost = min(c[i], c[j]) + min(c[i + 1], c[j – 1])
- secondCost = min(c[i], c[j – 1]) + min(c[i + 1], c[j])
- Choose minimum from them, add it to result.
Below is the implementation of the above idea:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum cost int solve( int n, string Str, int c[]) { int cost = 0; // Iterate from first and last for ( int i = 0, j = n - 1; i < j; i += 2, j -= 2) { if (Str[i] == Str[j] && Str[i + 1] == Str[j - 1]) continue ; if (Str[i] == Str[j - 1] && Str[i + 1] == Str[j]) continue ; // 1st condition int firstCost = 0, secondCost = 0; // Checking the cost minimum for each // and every option if (Str[i] != Str[j]) firstCost += min(c[i], c[j]); if (Str[i + 1] != Str[j - 1]) firstCost += min(c[i + 1], c[j - 1]); if (Str[i] != Str[j - 1]) secondCost += min(c[i], c[j - 1]); if (Str[i + 1] != Str[j]) secondCost += min(c[i + 1], c[j]); // Add minimum cost cost += min(firstCost, secondCost); } // Return the cost return cost; } // Driver code int main() { int n = 4; string Str = "bdbd"; int c[] = { 1, 2, 3, 4 }; // Function call cout << solve(n, Str, c); return 0; } |
Java
// Java code for the above approach: import java.util.*; public class Main { // Function to find the minimum cost public static int solve( int n, String Str, int [] c) { int cost = 0 ; // Iterate from first and last for ( int i = 0 , j = n - 1 ; i < j; i += 2 , j -= 2 ) { if (Str.charAt(i) == Str.charAt(j) && Str.charAt(i + 1 ) == Str.charAt(j - 1 )) continue ; if (Str.charAt(i) == Str.charAt(j - 1 ) && Str.charAt(i + 1 ) == Str.charAt(j)) continue ; // 1st condition int firstCost = 0 , secondCost = 0 ; // Checking the minimum cost for each and every // option if (Str.charAt(i) != Str.charAt(j)) firstCost += Math.min(c[i], c[j]); if (Str.charAt(i + 1 ) != Str.charAt(j - 1 )) firstCost += Math.min(c[i + 1 ], c[j - 1 ]); if (Str.charAt(i) != Str.charAt(j - 1 )) secondCost += Math.min(c[i], c[j - 1 ]); if (Str.charAt(i + 1 ) != Str.charAt(j)) secondCost += Math.min(c[i + 1 ], c[j]); // Add the minimum cost cost += Math.min(firstCost, secondCost); } // Return the cost return cost; } // Driver code public static void main(String[] args) { int n = 4 ; String Str = "bdbd" ; int [] c = { 1 , 2 , 3 , 4 }; // Function call System.out.println(solve(n, Str, c)); } } |
Python
# code added by flutterfly def solve(n, Str , c): cost = 0 # Iterate from first and last for i in range ( 0 , n - 1 , 2 ): j = n - 1 - i if Str [i] = = Str [j] and Str [i + 1 ] = = Str [j - 1 ]: continue if Str [i] = = Str [j - 1 ] and Str [i + 1 ] = = Str [j]: continue # 1st condition firstCost = 0 secondCost = 0 # Checking the cost minimum for each # and every option if Str [i] ! = Str [j]: firstCost + = min (c[i], c[j]) if Str [i + 1 ] ! = Str [j - 1 ]: firstCost + = min (c[i + 1 ], c[j - 1 ]) if Str [i] ! = Str [j - 1 ]: secondCost + = min (c[i], c[j - 1 ]) if Str [i + 1 ] ! = Str [j]: secondCost + = min (c[i + 1 ], c[j]) # Add minimum cost cost + = min (firstCost, secondCost) # Add minimum cost return cost # Driver code n = 4 Str = "bdbd" c = [ 1 , 2 , 3 , 4 ] # Function's call print (solve(n, Str , c)) |
C#
using System; class Program { // Function to find minimum cost static int Solve( int n, string Str, int [] c) { int cost = 0; // Iterate from first and last for ( int i = 0, j = n - 1; i < j; i += 2, j -= 2) { if (Str[i] == Str[j] && Str[i + 1] == Str[j - 1]) continue ; if (Str[i] == Str[j - 1] && Str[i + 1] == Str[j]) continue ; // 1st condition int firstCost = 0, secondCost = 0; // Checking the cost minimum for each // and every option if (Str[i] != Str[j]) firstCost += Math.Min(c[i], c[j]); if (Str[i + 1] != Str[j - 1]) firstCost += Math.Min(c[i + 1], c[j - 1]); if (Str[i] != Str[j - 1]) secondCost += Math.Min(c[i], c[j - 1]); if (Str[i + 1] != Str[j]) secondCost += Math.Min(c[i + 1], c[j]); // Add minimum cost cost += Math.Min(firstCost, secondCost); } // Return the cost return cost; } // Driver code static void Main() { int n = 4; string Str = "bdbd" ; int [] c = { 1, 2, 3, 4 }; // Function's Call Console.WriteLine(Solve(n, Str, c)); } } |
Javascript
// code added by Flutterfly // Function to find minimum cost function solve(n, Str, c) { let cost = 0; // Iterate from first and last for (let i = 0, j = n - 1; i < j; i += 2, j -= 2) { if (Str[i] == Str[j] && Str[i + 1] == Str[j - 1]) continue ; if (Str[i] == Str[j - 1] && Str[i + 1] == Str[j]) continue ; // 1st condition let firstCost = 0, secondCost = 0; // Checking the cost minimum for each // and every option if (Str[i] != Str[j]) firstCost += Math.min(c[i], c[j]); if (Str[i + 1] != Str[j - 1]) firstCost += Math.min(c[i + 1], c[j - 1]); if (Str[i] != Str[j - 1]) secondCost += Math.min(c[i], c[j - 1]); if (Str[i + 1] != Str[j]) secondCost += Math.min(c[i + 1], c[j]); // Add minimum cost cost += Math.min(firstCost, secondCost); } // Return the cost return cost; } // Driver code const n = 4; const Str = "bdbd" ; const c = [1, 2, 3, 4]; // Function's Call console.log(solve(n, Str, c)); |
0
Time Complexity: O(n)
Auxiliary Space: O(1)