Check if it is possible to form string B from A under the given constraints | Java implementation of the approach ; Function that returns true if it is possible to form B from A satisfying the given conditions ; List to store the frequency of characters in A ; Vector to store the count of characters used from a particular group of characters ; Store the frequency of the characters ; If a character in B is not present in A ; If count of characters used from a particular group of characters exceeds m ; Update low to the starting index of the next group ; If count of characters used from a particular group of characters has not exceeded m ; Driver code
import java . io . * ; import java . util . * ; class GFG { static boolean isPossible ( String A , String B , int b , int m ) { List < List < Integer > > S = new ArrayList < List < Integer > > ( ) ; for ( int i = 0 ; i < 26 ; i ++ ) S . add ( new ArrayList < Integer > ( ) ) ; int [ ] box = new int [ A . length ( ) ] ; for ( int i = 0 ; i < A . length ( ) ; i ++ ) { S . get ( A . charAt ( i ) - ' a ' ) . add ( i ) ; } int low = 0 ; for ( int i = 0 ; i < B . length ( ) ; i ++ ) { List < Integer > indexes = S . get ( B . charAt ( i ) - ' a ' ) ; int it = lower_bound ( indexes , low ) ; if ( it == indexes . size ( ) ) return false ; int count = indexes . get ( it ) / b ; box [ count ] = box [ count ] + 1 ; if ( box [ count ] >= m ) { count ++ ; low = ( count ) * b ; } else low = indexes . get ( it ) + 1 ; } return true ; } static int lower_bound ( List < Integer > indexes , int k ) { int low = 0 , high = indexes . size ( ) - 1 ; while ( low < high ) { int mid = ( low + high ) / 2 ; if ( indexes . get ( mid ) < k ) low = mid + 1 ; else high = mid ; } return ( indexes . get ( low ) < k ) ? low + 1 : low ; } public static void main ( String [ ] args ) { String A = " abcbbcdefxyz " ; String B = " acdxyz " ; int b = 5 ; int m = 2 ; if ( isPossible ( A , B , b , m ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }