Minimum cost to generate any permutation of the given string | Java program for the above approach ; Function to find the minimum cost to form any permutation of string s ; Base Case ; Return the precomputed state ; Iterate over the string and check all possible characters available for current position ; Check if character can be placed at current position ; As there is no previous character so the cost for 1 st character is 0 ; Find the cost of current character and move to next position ; Store the answer for each current state ; Function that returns true if the current bit is set ; Function that generates any permutation of the given string with minimum cost ; Initialize dp table ; Set all the bits of the current character id ; Minimum cost of generating the permutation ; Driver Code ; Function Call
import java . util . * ; public class Main { public static int solve ( int a [ ] [ ] , String s , int n , int prev , int mask , int [ ] [ ] dp ) { if ( mask == 0 ) return 0 ; if ( dp [ mask ] [ prev + 1 ] != - 1 ) return dp [ mask ] [ prev + 1 ] ; int ans = 10000 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int id = s . charAt ( i ) - ' a ' ; if ( check ( mask , id ) ) { if ( prev == - 1 ) { ans = Math . min ( ans , solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; } else { ans = Math . min ( ans , a [ prev ] [ id ] + solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; } } } dp [ mask ] [ prev + 1 ] = ans ; return ans ; } public static boolean check ( int mask , int i ) { int c = ( mask & ( 1 << i ) ) ; return c != 0 ; } static void generatePermutation ( int mask , int n , int a [ ] [ ] , String s ) { int dp [ ] [ ] = new int [ ( 1 << n ) + 5 ] [ n + 5 ] ; for ( int i [ ] : dp ) Arrays . fill ( i , - 1 ) ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int id = s . charAt ( i ) - ' a ' ; mask |= ( 1 << id ) ; } System . out . println ( solve ( a , s , n , - 1 , mask , dp ) ) ; } public static void main ( String args [ ] ) { int N = 5 ; String str = " abcde " ; int mat [ ] [ ] = { { 0 , 5 , 1 , 5 , 3 } , { 4 , 0 , 9 , 4 , 2 } , { 7 , 9 , 0 , 10 , 7 } , { 1 , 2 , 8 , 0 , 2 } , { 3 , 9 , 7 , 7 , 0 } } ; generatePermutation ( 0 , N , mat , str ) ; } }