Check if it is possible to form string B from A under the given constraints | 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 ;
def isPossible ( A , B , b , m ) : NEW_LINE INDENT S = [ ] NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT S . append ( [ ] ) NEW_LINE DEDENT box = [ 0 ] * len ( A ) NEW_LINE for i in range ( len ( A ) ) : NEW_LINE INDENT S [ ord ( A [ i ] ) - ord ( ' a ' ) ] . append ( i ) NEW_LINE DEDENT low = 0 NEW_LINE for i in range ( len ( B ) ) : NEW_LINE INDENT indexes = S [ ord ( B [ i ] ) - ord ( ' a ' ) ] NEW_LINE it = lower_bound ( indexes , low ) NEW_LINE if ( it == len ( indexes ) ) : NEW_LINE INDENT return False NEW_LINE DEDENT count = indexes [ it ] // b NEW_LINE box [ count ] = box [ count ] + 1 NEW_LINE if ( box [ count ] >= m ) : NEW_LINE INDENT count += 1 NEW_LINE low = ( count ) * b NEW_LINE DEDENT else : NEW_LINE INDENT low = indexes [ it ] + 1 NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def lower_bound ( indexes , k ) : NEW_LINE INDENT low , high = 0 , len ( indexes ) - 1 NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( indexes [ mid ] < k ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT if indexes [ low ] < k : NEW_LINE INDENT return ( low + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return low NEW_LINE DEDENT DEDENT / * Driver code * / NEW_LINE A = " abcbbcdefxyz " NEW_LINE B = " acdxyz " NEW_LINE b = 5 NEW_LINE m = 2 NEW_LINE if ( isPossible ( A , B , b , m ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT