Minimum size substring to be removed to make a given string palindromic | C ++ program of the above approach ; Function to find palindromic prefix of maximum length ; Finding palindromic prefix of maximum length ; Checking if curr substring is palindrome or not . ; Condition to check if the prefix is a palindrome ; if no palindrome exist ; Function to find the maximum size palindrome such that after removing minimum size substring ; Finding prefix and suffix of same length ; Matching the ranges ; Case 1 : Length is even and whole string is palindrome ; Case 2 : Length is odd and whole string is palindrome ; Adding that mid character ; Add prefix or suffix of the remaining string or suffix , whichever is longer ; Reverse the remaining string to find the palindromic suffix ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string palindromePrefix ( string S ) { int n = S . size ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { string curr = S . substr ( 0 , i + 1 ) ; int l = 0 , r = curr . size ( ) - 1 ; bool is_palindrome = 1 ; while ( l < r ) { if ( curr [ l ] != curr [ r ] ) { is_palindrome = 0 ; break ; } l ++ ; r -- ; } if ( is_palindrome ) return curr ; } return " " ; } string maxPalindrome ( string S ) { int n = S . size ( ) ; if ( n <= 1 ) { return S ; } string pre = " " , suff = " " ; int i = 0 , j = n - 1 ; while ( S [ i ] == S [ j ] && i < j ) { i ++ ; j -- ; } i -- ; j ++ ; pre = S . substr ( 0 , i + 1 ) ; suff = S . substr ( j ) ; if ( j - i == 1 ) { return pre + suff ; } if ( j - i == 2 ) { string mid_char = S . substr ( i + 1 , 1 ) ; return pre + mid_char + suff ; } string rem_str = S . substr ( i + 1 , j - i - 1 ) ; string pre_of_rem_str = palindromePrefix ( rem_str ) ; reverse ( rem_str . begin ( ) , rem_str . end ( ) ) ; string suff_of_rem_str = palindromePrefix ( rem_str ) ; if ( pre_of_rem_str . size ( ) >= suff_of_rem_str . size ( ) ) { return pre + pre_of_rem_str + suff ; } else { return pre + suff_of_rem_str + suff ; } } int main ( ) { string S = " geeksforskeeg " ; cout << maxPalindrome ( S ) ; return 0 ; }