Check if string S2 can be obtained by appending subsequences of string S1 | C ++ Program to implement the above approach ; Function for finding minimum number of operations ; Stores the length of strings ; Stores frequency of characters in string s ; Update frequencies of character in s ; Traverse string s1 ; If any character in s1 is not present in s ; Stores the indices of each character in s ; Traverse string s ; Store indices of characters ; Stores index of last appended character ; Traverse string s1 ; Find the index of next character that can be appended ; Check if the current character be included in the current subsequence ; Otherwise ; Start a new subsequence ; Update index of last character appended ; Driver Code ; If S2 cannot be obtained from subsequences of S1 ; Otherwise
#include " bits / stdc + + . h " NEW_LINE using namespace std ; int findMinimumOperations ( string s , string s1 ) { int n = s . length ( ) , m = s1 . length ( ) ; int frequency [ 26 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) frequency [ s [ i ] - ' a ' ] ++ ; for ( int i = 0 ; i < m ; i ++ ) { if ( frequency [ s1 [ i ] - ' a ' ] == 0 ) { return -1 ; } } set < int > indices [ 26 ] ; for ( int i = 0 ; i < n ; i ++ ) { indices [ s [ i ] - ' a ' ] . insert ( i ) ; } int ans = 1 ; int last = ( * indices [ s1 [ 0 ] - ' a ' ] . begin ( ) ) ; for ( int i = 1 ; i < m ; i ++ ) { int ch = s1 [ i ] - ' a ' ; auto it = indices [ ch ] . upper_bound ( last ) ; if ( it != indices [ ch ] . end ( ) ) { last = ( * it ) ; } else { ans ++ ; last = ( * indices [ ch ] . begin ( ) ) ; } } return ans ; } int main ( ) { string S1 = " acebcd " , S2 = " acbcde " ; int ans = findMinimumOperations ( S1 , S2 ) ; if ( ans == -1 ) { cout << " NO STRNEWLINE " ; } else { cout << " YES STRNEWLINE " << ans ; } return 0 ; }