Minimize cost to convert given string to a palindrome | C ++ program for the above approach ; Function to find the minimum cost to convert the string into a palindrome ; Length of the string ; If iointer is in the second half ; Reverse the string ; Pointing to initial position ; Find the farthest index needed to change on left side ; Find the farthest index needed to change on right side ; Changing the variable to make string palindrome ; min distance to travel to make string palindrome ; Total cost ; Return the minimum cost ; Driver Code ; Given string S ; Given pointer P ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinCost ( string str , int pos ) { int n = str . length ( ) ; if ( pos >= n / 2 ) { reverse ( str . begin ( ) , str . end ( ) ) ; pos = n - pos - 1 ; } int left , right ; left = right = pos ; for ( int i = pos ; i >= 0 ; -- i ) { if ( str [ i ] != str [ n - i - 1 ] ) { left = i ; } } 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 ) { if ( str [ i ] != str [ n - i - 1 ] ) ans += 1 ; } int dis = min ( ( 2 * ( pos - left ) + ( right - pos ) ) , ( 2 * ( right - pos ) + ( pos - left ) ) ) ; ans = ans + dis ; return ans ; } int main ( ) { string S = " bass " ; int P = 3 ; cout << findMinCost ( S , P ) ; return 0 ; }