Minimum steps to delete a string by deleting substring comprising of same characters | C ++ implementation of the approach ; Function to return the minimum number of delete operations ; When a single character is deleted ; When a group of consecutive characters are deleted if any of them matches ; When both the characters are same then delete the letters in between them ; Memoize ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 10 ; int findMinimumDeletion ( int l , int r , int dp [ N ] [ N ] , string s ) { if ( l > r ) return 0 ; if ( l == r ) return 1 ; if ( dp [ l ] [ r ] != -1 ) return dp [ l ] [ r ] ; int res = 1 + findMinimumDeletion ( l + 1 , r , dp , s ) ; for ( int i = l + 1 ; i <= r ; ++ i ) { if ( s [ l ] == s [ i ] ) res = min ( res , findMinimumDeletion ( l + 1 , i - 1 , dp , s ) + findMinimumDeletion ( i , r , dp , s ) ) ; } return dp [ l ] [ r ] = res ; } int main ( ) { string s = " abcddcba " ; int n = s . length ( ) ; int dp [ N ] [ N ] ; memset ( dp , -1 , sizeof dp ) ; cout << findMinimumDeletion ( 0 , n - 1 , dp , s ) ; return 0 ; }