Minimum operation require to make first and last character same | CPP program to find minimum operation require to make first and last character same ; Function to find minimum operation require to make first and last character same ; Base conditions ; If answer found ; If string is already visited ; Decrement ending index only ; Increment starting index only ; Increment starting index and decrement index ; Store the minimum value ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = INT_MAX ; map < string , int > m ; int Min = INT_MAX ; int minOperation ( string & s , int i , int j , int count ) { if ( ( i >= s . size ( ) && j < 0 ) || ( i == j ) ) return MAX ; if ( s [ i ] == s [ j ] || ( count >= Min ) ) return count ; string str = to_string ( i ) + " | " + to_string ( j ) ; if ( m . find ( str ) == m . end ( ) ) { if ( i >= s . size ( ) ) m [ str ] = minOperation ( s , i , j - 1 , count + 1 ) ; else if ( j < 0 ) m [ str ] = minOperation ( s , i + 1 , j , count + 1 ) ; else m [ str ] = min ( minOperation ( s , i , j - 1 , count + 1 ) , minOperation ( s , i + 1 , j , count + 1 ) ) ; } if ( m [ str ] < Min ) Min = m [ str ] ; return m [ str ] ; } int main ( ) { string s = " bacdefghipalop " ; int ans = minOperation ( s , 0 , s . size ( ) - 1 , 0 ) ; if ( ans == MAX ) cout << -1 ; else cout << ans ; }