Minimize steps to form string S from any random string of length K using a fixed length subsequences | Java code for above approach ; Function to find the minimum number of string required to generate the original string ; Stores the frequency of each character of string S ; Iterate over the range [ 0 , 25 ] ; Stores the frequency of each character of string S ; Count unique characters in S ; If unique characters is greater then N , then return - 1 ; Otherwise ; Perform Binary Search ; Find the value of mid ; Iterate over the range [ 0 , 26 ] ; If the amount [ i ] is greater than 0 ; Update the ranges ; Find the resultant string ; Generate the subsequence ; If the length of resultant string is less than N than add a character ' a ' ; Print the string ; Driver Code
import java . util . * ; class GFG { static void findString ( String S , int N ) { int [ ] amounts = new int [ 26 ] ; for ( int i = 0 ; i < 26 ; i ++ ) { amounts [ i ] = 0 ; } for ( int i = 0 ; i < S . length ( ) ; i ++ ) { amounts [ ( int ) ( S . charAt ( i ) - 97 ) ] ++ ; } int count = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( amounts [ i ] > 0 ) count ++ ; } if ( count > N ) { System . out . print ( " - 1" ) ; } else { String ans = " " ; int high = 100001 ; int low = 0 ; int mid , total ; while ( ( high - low ) > 1 ) { total = 0 ; mid = ( high + low ) / 2 ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( amounts [ i ] > 0 ) { total += ( amounts [ i ] - 1 ) / mid + 1 ; } } if ( total <= N ) { high = mid ; } else { low = mid ; } } System . out . print ( high + " ▁ " ) ; total = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( amounts [ i ] > 0 ) { total += ( amounts [ i ] - 1 ) / high + 1 ; for ( int j = 0 ; j < ( ( amounts [ i ] - 1 ) / high + 1 ) ; j ++ ) { ans += ( char ) ( i + 97 ) ; } } } for ( int i = total ; i < N ; i ++ ) { ans += ' a ' ; } String reverse = " " ; int Len = ans . length ( ) - 1 ; while ( Len >= 0 ) { reverse = reverse + ans . charAt ( Len ) ; Len -- ; } System . out . print ( reverse ) ; } } public static void main ( String [ ] args ) { String S = " toffee " ; int K = 4 ; findString ( S , K ) ; } }