Minimum subsequences of a string A required to be appended to obtain the string B | C ++ program for the above approach ; Function to count the minimum subsequences of a string A required to be appended to obtain the string B ; Size of the string ; Maps characters to their respective indices ; Insert indices of characters into the sets ; Stores the position of the last visited index in the string A . Initially set it to - 1. ; Stores the required count ; Iterate over the characters of B ; If the character in B is not present in A , return - 1 ; Fetch the next index from B [ i ] 's set ; If the iterator points to the end of that set ; If it doesn 't point to the  end, update previous ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countminOpsToConstructAString ( string A , string B ) { int N = A . length ( ) ; int i = 0 ; map < char , set < int > > mp ; for ( i = 0 ; i < N ; i ++ ) { mp [ A [ i ] ] . insert ( i ) ; } int previous = -1 ; int ans = 1 ; for ( i = 0 ; i < B . length ( ) ; i ++ ) { char ch = B [ i ] ; if ( mp [ ch ] . size ( ) == 0 ) { cout << -1 ; return ; } auto it = mp [ ch ] . upper_bound ( previous ) ; if ( it == mp [ ch ] . end ( ) ) { previous = -1 ; ans ++ ; -- i ; continue ; } previous = * it ; } cout << ans ; } int main ( ) { string A = " abc " , B = " abac " ; countminOpsToConstructAString ( A , B ) ; return 0 ; }