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 ; Vector 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( string A , string B , int b , int m ) { vector < int > S [ 26 ] ; vector < int > box ( A . length ( ) , 0 ) ; for ( int i = 0 ; i < A . length ( ) ; i ++ ) { S [ A [ i ] - ' a ' ] . push_back ( i ) ; } int low = 0 ; for ( int i = 0 ; i < B . length ( ) ; i ++ ) { auto it = lower_bound ( S [ B [ i ] - ' a ' ] . begin ( ) , S [ B [ i ] - ' a ' ] . end ( ) , low ) ; if ( it == S [ B [ i ] - ' a ' ] . end ( ) ) return false ; int count = ( * it ) / b ; box [ count ] = box [ count ] + 1 ; if ( box [ count ] >= m ) { count ++ ; low = ( count ) * b ; } else low = ( * it ) + 1 ; } return true ; } int main ( ) { string A = " abcbbcdefxyz " ; string B = " acdxyz " ; int b = 5 ; int m = 2 ; if ( isPossible ( A , B , b , m ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }