Minimum number of characters required to be added to a String such that all lowercase alphabets occurs as a subsequence in increasing order | C ++ program for the above approach ; Function to find the LCS of strings S and string T ; Base Case ; Already Calculated State ; If the characters are the same ; Otherwise ; Function to find the minimum number of characters that needs to be appended in the string to get all lowercase alphabets as a subsequences ; String containing all the characters ; Stores the result of overlapping subproblems ; Return the minimum characters required ; Driver Code
#include " bits / stdc + + . h " NEW_LINE using namespace std ; int LCS ( string & S , int N , string & T , int M , vector < vector < int > > & dp ) { if ( N == 0 or M == 0 ) return 0 ; if ( dp [ N ] [ M ] != -1 ) return dp [ N ] [ M ] ; if ( S [ N - 1 ] == T [ M - 1 ] ) { return dp [ N ] [ M ] = 1 + LCS ( S , N - 1 , T , M - 1 , dp ) ; } return dp [ N ] [ M ] = max ( LCS ( S , N - 1 , T , M , dp ) , LCS ( S , N , T , M - 1 , dp ) ) ; } int minimumCharacter ( string & S ) { string T = " abcdefghijklmnopqrstuvwxyz " ; int N = S . length ( ) , M = T . length ( ) ; vector < vector < int > > dp ( N + 1 , vector < int > ( M + 1 , -1 ) ) ; return ( 26 - LCS ( S , N , T , M , dp ) ) ; } int main ( ) { string S = " abcdadc " ; cout << minimumCharacter ( S ) ; return 0 ; }