Minimum number of characters required to be added to a String such that all lowercase alphabets occurs as a subsequence in increasing order | Java 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
import java . io . * ; class GFG { static int LCS ( String S , int N , String T , int M , int dp [ ] [ ] ) { if ( N == 0 M == 0 ) return 0 ; if ( dp [ N ] [ M ] != 0 ) return dp [ N ] [ M ] ; if ( S . charAt ( N - 1 ) == T . charAt ( M - 1 ) ) { return dp [ N ] [ M ] = 1 + LCS ( S , N - 1 , T , M - 1 , dp ) ; } return dp [ N ] [ M ] = Math . max ( LCS ( S , N - 1 , T , M , dp ) , LCS ( S , N , T , M - 1 , dp ) ) ; } static int minimumCharacter ( String S ) { String T = " abcdefghijklmnopqrstuvwxyz " ; int N = S . length ( ) , M = T . length ( ) ; int dp [ ] [ ] = new int [ N + 1 ] [ M + 1 ] ; return ( 26 - LCS ( S , N , T , M , dp ) ) ; } public static void main ( String [ ] args ) { String S = " abcdadc " ; System . out . println ( minimumCharacter ( S ) ) ; } }