Construct a string that has exactly K subsequences from given string | Python3 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 output ; Print the string ; Driver code ; Given String ; Function Call
import math NEW_LINE def printSubsequenceString ( st , k ) : NEW_LINE INDENT n = len ( st ) NEW_LINE factors = [ ] NEW_LINE sqt = ( int ( math . sqrt ( k ) ) ) NEW_LINE for i in range ( 2 , sqt + 1 ) : NEW_LINE INDENT while ( k % i == 0 ) : NEW_LINE INDENT factors . append ( i ) NEW_LINE k //= i NEW_LINE DEDENT DEDENT if ( k > 1 ) : NEW_LINE INDENT factors . append ( k ) NEW_LINE DEDENT count = [ 1 ] * n NEW_LINE index = 0 NEW_LINE while ( len ( factors ) > 0 ) : NEW_LINE INDENT count [ index ] *= factors [ - 1 ] NEW_LINE factors . pop ( ) NEW_LINE index += 1 NEW_LINE if ( index == n ) : NEW_LINE INDENT index = 0 NEW_LINE DEDENT DEDENT s = " " NEW_LINE for i in range ( n ) : NEW_LINE INDENT while ( count [ i ] > 0 ) : NEW_LINE INDENT s += st [ i ] NEW_LINE count [ i ] -= 1 NEW_LINE DEDENT DEDENT print ( s ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " code " NEW_LINE k = 20 NEW_LINE printSubsequenceString ( st , k ) NEW_LINE DEDENT