Given a string S of length N and an integer P denoting a pointer to Pth index of the string, the task is to find the minimum cost to convert the string into a palindrome by performing the following operations:
- Pointer P can be moved from index i to index j and the cost required is |i – j| where 0 ? i < N and 0 ? j < N.
- The cost to change the character at the Pth index is 1.
Examples:
Input: S = “saad”, P = 1
Output: 2
Explanation:
Initially the pointer is at index 1.
Step 1: Move pointer to index 0. Therefore, cost = 1 – 0 = 1.
Step 2: Change character s to d. Therefore, cost = 1 + 1 = 2 and S = “daad”
Hence, the cost is 2.Input: S = “bass”, P = 3
Output: 3
Explanation:
Initially the pointer is at index 3.
Step 1: Change character at index P = 3 to b. Therefore, cost = 1 and S = “basb”.
Step 2: Move pointer to index 2. Therefore, cost = 1 + 1 = 2.
Step 3: Change character at index P = 2 to a. Therefore, cost = 3 and S = “baab”
Hence, the cost is 3.
Approach: The idea is to find the first and the last character that needs to be changed in the first half of the string when the pointer is in the first half or reverse the string if the pointer is in the second half and adjust the pointer accordingly. Follow the below steps to solve the problem:
- If the pointer is in the second half then reverse the string and change the pointer to (N – 1 – P).
- Now, find the farthest character’s position needed to change at the left and right side in the first half of the string. Let them be l and r.
- Find the total cost to change the characters i.e., total characters in the first half such that S[i] != s[N – i – 1] where 0 < i < N/2.
- The minimum distance traverse to change the characters is min(2*(P – l) + r – P, 2*(r – P) + P – l).
- Print the answer as the sum of the cost to change the characters and minimum distance to travel.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost to// convert the string into a palindromeint findMinCost(string str, int pos){ // Length of the string int n = str.length(); // If iointer is in the second half if (pos >= n / 2) { // Reverse the string reverse(str.begin(), str.end()); pos = n - pos - 1; } int left, right; // Pointing to initial position left = right = pos; // Find the farthest index needed to // change on left side for (int i = pos; i >= 0; --i) { if (str[i] != str[n - i - 1]) { left = i; } } // Find the farthest index needed to // change on right side for (int i = pos; i < n / 2; ++i) { if (str[i] != str[n - i - 1]) { right = i; } } int ans = 0; for (int i = left; i <= right; ++i) { // Changing the variable to make // string palindrome if (str[i] != str[n - i - 1]) ans += 1; } // min distance to travel to make // string palindrome int dis = min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left))); // Total cost ans = ans + dis; // Return the minimum cost return ans;}// Driver Codeint main(){ // Given string S string S = "bass"; // Given pointer P int P = 3; // Function Call cout << findMinCost(S, P); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the minimum cost to// convert the string into a palindromestatic int findMinCost(String str, int pos){ // Length of the string int n = str.length(); StringBuilder input1 = new StringBuilder(); input1.append(str); // If iointer is in the second half if (pos >= n / 2) { // Reverse the string input1 = input1.reverse(); pos = n - pos - 1; } int left, right; // Pointing to initial position left = right = pos; // Find the farthest index needed to // change on left side for(int i = pos; i >= 0; --i) { if (input1.charAt(i) != input1.charAt(n - i - 1)) { left = i; } } // Find the farthest index needed to // change on right side for(int i = pos; i < n / 2; ++i) { if (input1.charAt(i) != input1.charAt(n - i - 1)) { right = i; } } int ans = 0; for(int i = left; i <= right; ++i) { // Changing the variable to make // string palindrome if (input1.charAt(i) != input1.charAt(n - i - 1)) ans += 1; } // min distance to travel to make // string palindrome int dis = Math.min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left))); // Total cost ans = ans + dis; // Return the minimum cost return ans;}// Driver Codepublic static void main(String args[]){ // Given string S String S = "bass"; // Given pointer P int P = 3; // Function Call System.out.println(findMinCost(S, P));}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approach# Function to find the minimum cost to# convert the into a palindromedef findMinCost(strr, pos): # Length of the string n = len(strr) # If iointer is in the second half if (pos >= n / 2): # Reverse the string strr = strr[::-1] pos = n - pos - 1 left, right = pos, pos # Pointing to initial position # left = right = pos # Find the farthest index needed # to change on left side for i in range(pos, -1, -1): if (strr[i] != strr[n - i - 1]): left = i # Find the farthest index needed # to change on right side for i in range(pos, n // 2): if (strr[i] != strr[n - i - 1]): right = i ans = 0 for i in range(left, right + 1): # Changing the variable to make # palindrome if (strr[i] != strr[n - i - 1]): ans += 1 # min distance to travel to make # palindrome dis = (min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left)))) # Total cost ans = ans + dis # Return the minimum cost return ans# Driver Codeif __name__ == '__main__': # Given S S = "bass" # Given pointer P P = 3 # Function Call print(findMinCost(S, P))# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;class GFG{ // Function to find the minimum // cost to convert the string // into a palindromestatic int findMinCost(string str, int pos){ // Length of the string int n = str.Length; char[] charArray = str.ToCharArray(); // If iointer is in the // second half if (pos >= n / 2) { // Reverse the string Array.Reverse(charArray); pos = n - pos - 1; } int left, right; // Pointing to initial position left = right = pos; // Find the farthest index // needed to change on // left side for(int i = pos; i >= 0; --i) { if (charArray[i] != charArray[n - i - 1]) { left = i; } } // Find the farthest index // needed to change on right // side for(int i = pos; i < n / 2; ++i) { if (charArray[i] != charArray[n - i - 1]) { right = i; } } int ans = 0; for(int i = left; i <= right; ++i) { // Changing the variable to make // string palindrome if (charArray[i]!= charArray[n - i - 1]) ans += 1; } // min distance to travel to make // string palindrome int dis = Math.Min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left))); // Total cost ans = ans + dis; // Return the minimum cost return ans;}// Driver Codepublic static void Main(){ // Given string S string S = "bass"; // Given pointer P int P = 3; // Function Call Console.Write(findMinCost(S, P));}}// This code is contributed by Chitranayal |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum cost to// convert the string into a palindromefunction findMinCost(str, pos){ // Length of the string var n = str.length; // If iointer is in the second half if (pos >= n / 2) { // Reverse the string str.split('').reverse().fill(''); pos = n - pos - 1; } var left, right; // Pointing to initial position left = right = pos; // Find the farthest index needed to // change on left side for(var i = pos; i >= 0; --i) { if (str[i] != str[n - i - 1]) { left = i; } } // Find the farthest index needed to // change on right side for(var i = pos; i < n / 2; ++i) { if (str[i] != str[n - i - 1]) { right = i; } } var ans = 0; for(var i = left; i <= right; ++i) { // Changing the variable to make // string palindrome if (str[i] != str[n - i - 1]) ans += 1; } // min distance to travel to make // string palindrome var dis = Math.min((2 * (pos - left) + (right - pos)), (2 * (right - pos) + (pos - left))); // Total cost ans = ans + dis; // Return the minimum cost return ans;}// Driver Code// Given string Svar S = "bass";// Given pointer Pvar P = 3;// Function Calldocument.write(findMinCost(S, P));// This code is contributed by itsok</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
