Construct a string that has exactly K subsequences from given string | C ++ program for the above approach ; Function that computes the string s ; Length of the given string str ; List that stores all the prime factors of given k ; Find the prime factors ; Initialize the count of each character position as 1 ; Loop until the list becomes empty ; Increase the character count by multiplying it with the prime factor ; If we reach end then again start from beginning ; Store the output ; Print the string ; Driver code ; Given String ; Function Call
#include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; void printSubsequenceString ( string str , long long k ) { int n = str . size ( ) ; int i ; vector < long long > factors ; for ( long long i = 2 ; i <= sqrt ( k ) ; i ++ ) { while ( k % i == 0 ) { factors . push_back ( i ) ; k /= i ; } } if ( k > 1 ) factors . push_back ( k ) ; vector < long long > count ( n , 1 ) ; int index = 0 ; while ( factors . size ( ) > 0 ) { count [ index ++ ] *= factors . back ( ) ; factors . pop_back ( ) ; if ( index == n ) index = 0 ; } string s ; for ( i = 0 ; i < n ; i ++ ) { while ( count [ i ] -- > 0 ) { s += str [ i ] ; } } cout << s ; } int main ( ) { string str = " code " ; long long k = 20 ; printSubsequenceString ( str , k ) ; return 0 ; }