Check if it is possible to form string B from A under the given constraints | C # 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
using System ; using System . Collections . Generic ; class GFG { static bool isPossible ( string A , string B , int b , int m ) { List < List < int > > S = new List < List < int > > ( ) ; for ( int i = 0 ; i < 26 ; i ++ ) { S . Add ( new List < int > ( ) ) ; } int [ ] box = new int [ A . Length ] ; for ( int i = 0 ; i < A . Length ; i ++ ) { S [ A [ i ] - ' a ' ] . Add ( i ) ; } int low = 0 ; for ( int i = 0 ; i < B . Length ; i ++ ) { List < int > indexes = S [ B [ i ] - ' a ' ] ; int it = lower_bound ( indexes , low ) ; if ( it == indexes . Count ) return false ; int count = indexes [ it ] / b ; box [ count ] = box [ count ] + 1 ; if ( box [ count ] >= m ) { count ++ ; low = ( count ) * b ; } else low = indexes [ it ] + 1 ; } return true ; } static int lower_bound ( List < int > indexes , int k ) { int low = 0 , high = indexes . Count - 1 ; while ( low < high ) { int mid = ( low + high ) / 2 ; if ( indexes [ mid ] < k ) low = mid + 1 ; else high = mid ; } return ( indexes [ low ] < k ) ? low + 1 : low ; } static void Main ( ) { string A = " abcbbcdefxyz " ; string B = " acdxyz " ; int b = 5 ; int m = 2 ; if ( isPossible ( A , B , b , m ) ) Console . WriteLine ( " Yes " ) ; else Console . WriteLine ( " No " ) ; } }