Minimum number of subsequences required to convert one string to another | C ++ program to find the Minimum number of subsequences required to convert one string to another ; Function to find the no of subsequences ; Push the values of indexes of each character ; Find the next index available in the array ; If Character is not in string A ; Check if the next index is not equal to the size of array which means there is no index greater than minIndex in the array ; Update value of minIndex with this index ; Update the value of counter and minIndex for next operation ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSubsequnces ( string A , string B ) { vector < int > v [ 26 ] ; int minIndex = -1 , cnt = 1 , j = 0 ; int flag = 0 ; for ( int i = 0 ; i < A . length ( ) ; i ++ ) { int p = ( int ) A [ i ] - 97 ; v [ p ] . push_back ( i ) ; } while ( j < B . length ( ) ) { int p = ( int ) B [ j ] - 97 ; int k = upper_bound ( v [ p ] . begin ( ) , v [ p ] . end ( ) , minIndex ) - v [ p ] . begin ( ) ; if ( v [ p ] . size ( ) == 0 ) { flag = 1 ; break ; } if ( k != v [ p ] . size ( ) ) { minIndex = v [ p ] [ k ] ; j = j + 1 ; } else { cnt = cnt + 1 ; minIndex = -1 ; } } if ( flag == 1 ) { return -1 ; } return cnt ; } int main ( ) { string A1 = " abbace " ; string B1 = " acebbaae " ; cout << minSubsequnces ( A1 , B1 ) << endl ; return 0 ; }