Remove minimum characters from string to split it into three substrings under given constraints | C ++ program for the above approach ; Function that counts minimum character that must be removed ; Length of string ; Create prefix array ; Initialize first position ; Fill prefix array ; Initialise maxi ; Check all the possibilities by putting i and j at different position & find maximum among them ; Print the characters to be removed ; Driver Code ; Given String ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void min_remove ( string str ) { int N = str . length ( ) ; int prefix_a [ N + 1 ] ; int prefix_b [ N + 1 ] ; int prefix_c [ N + 1 ] ; prefix_a [ 0 ] = 0 ; prefix_b [ 0 ] = 0 ; prefix_c [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { prefix_a [ i ] = prefix_a [ i - 1 ] + ( str [ i - 1 ] == ' a ' ) ; prefix_b [ i ] = prefix_b [ i - 1 ] + ( str [ i - 1 ] == ' b ' ) ; prefix_c [ i ] = prefix_c [ i - 1 ] + ( str [ i - 1 ] == ' c ' ) ; } int maxi = INT_MIN ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int j = i ; j <= N ; j ++ ) { maxi = max ( maxi , ( prefix_a [ i ] + ( prefix_b [ j ] - prefix_b [ i ] ) + ( prefix_c [ N ] - prefix_c [ j ] ) ) ) ; } } cout << ( N - maxi ) << endl ; } int main ( ) { string str = " aaaabaaxccac " ; min_remove ( str ) ; return 0 ; }