Given a string str and an integer K, the task is to find a string S such that it has exactly K subsequences of given string str.
Examples:
Input: str = “gfg”, K = 10
Output: gggggffg
Explanation:
There are 10 possible subsequence of the given string “gggggffg”. They are:
1. gggggffg
2. gggggffg
3. gggggffg
4. gggggffg
5. gggggffg
6. gggggffg
7. gggggffg
8. gggggffg
9. gggggffg
10. gggggffg.
Input: str = “code”, K = 20
Output: cccccoodde
Explanation:
There are 20 possible subsequence of the string “cccccoodde”.
Approach:
To solve the problem mentioned above we have to follow the steps given below:
- The idea is to find the prime factors of K and store the prime factors(say factors).
- Create an empty array count of the size of the given string to store the count of each character in the resultant string s. Initialize the array with 1.
- Now pop elements from the list factors and multiply to each position of array in a cyclic way until the list becomes empty. Finally, we have the count of each character of str in the array.
- Iterate in the array count[] and append the number of characters for each character ch to the resultant string s.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// Function that computes the string svoid printSubsequenceString(string str, long long k){ // Length of the given string str int n = str.size(); int i; // List that stores all the prime // factors of given k vector<long long> factors; // Find the prime 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); // Initialize the count of each // character position as 1 vector<long long> count(n, 1); int index = 0; // Loop until the list // becomes empty while (factors.size() > 0) { // Increase the character // count by multiplying it // with the prime factor count[index++] *= factors.back(); factors.pop_back(); // If we reach end then again // start from beginning if (index == n) index = 0; } // Store the output string s; for (i = 0; i < n; i++) { while (count[i]-- > 0) { s += str[i]; } } // Print the string cout << s;}// Driver codeint main(){ // Given String string str = "code"; long long k = 20; // Function Call printSubsequenceString(str, k); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function that computes the String s static void printSubsequenceString(String str, int k) { // Length of the given String str int n = str.length(); int i; // List that stores all the prime // factors of given k Vector<Integer> factors = new Vector<Integer>(); // Find the prime factors for (i = 2; i <= Math.sqrt(k); i++) { while (k % i == 0) { factors.add(i); k /= i; } } if (k > 1) factors.add(k); // Initialize the count of each // character position as 1 int []count = new int[n]; Arrays.fill(count, 1); int index = 0; // Loop until the list // becomes empty while (factors.size() > 0) { // Increase the character // count by multiplying it // with the prime factor count[index++] *= factors.get(factors.size() - 1); factors.remove(factors.get(factors.size() - 1)); // If we reach end then again // start from beginning if (index == n) index = 0; } // Store the output String s = ""; for (i = 0; i < n; i++) { while (count[i]-- > 0) { s += str.charAt(i); } } // Print the String System.out.print(s); } // Driver code public static void main(String[] args) { // Given String String str = "code"; int k = 20; // Function Call printSubsequenceString(str, k); }} // This code is contributed by sapnasingh4991 |
Python3
# Python3 program for # the above approachimport math# Function that computes # the string sdef printSubsequenceString(st, k): # Length of the given # string str n = len(st) # List that stores # all the prime # factors of given k factors = [] # Find the prime factors sqt = (int(math.sqrt(k))) for i in range (2, sqt + 1): while (k % i == 0): factors.append(i) k //= i if (k > 1): factors.append(k) # Initialize the count of each # character position as 1 count = [1] * n index = 0 # Loop until the list # becomes empty while (len(factors) > 0): # Increase the character # count by multiplying it # with the prime factor count[index] *= factors[-1] factors.pop() index += 1 # If we reach end then again # start from beginning if (index == n): index = 0 # store output s = "" for i in range (n): while (count[i] > 0): s += st[i] count[i] -= 1 # Print the string print (s)# Driver codeif __name__ == "__main__": # Given String st = "code" k = 20 # Function Call printSubsequenceString(st, k) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function that computes the String s static void printSubsequenceString(String str, int k) { // Length of the given String str int n = str.Length; int i; // List that stores all the prime // factors of given k List<int> factors = new List<int>(); // Find the prime factors for (i = 2; i <= Math.Sqrt(k); i++) { while (k % i == 0) { factors.Add(i); k /= i; } } if (k > 1) factors.Add(k); // Initialize the count of each // character position as 1 int []count = new int[n]; for (i = 0; i < n; i++) count[i] = 1; int index = 0; // Loop until the list // becomes empty while (factors.Count > 0) { // Increase the character // count by multiplying it // with the prime factor count[index++] *= factors[factors.Count - 1]; factors.Remove(factors[factors.Count - 1]); // If we reach end then again // start from beginning if (index == n) index = 0; } // Store the output String s = ""; for (i = 0; i < n; i++) { while (count[i]-- > 0) { s += str[i]; } } // Print the String Console.Write(s); } // Driver code public static void Main(String[] args) { // Given String String str = "code"; int k = 20; // Function Call printSubsequenceString(str, k); }} // This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program for the above approach// Function that computes the string sfunction printSubsequenceString(str, k){ // Length of the given string str let n = str.length; let i; // List that stores all the prime // factors of given k let factors = new Array(); // Find the prime factors for (let i = 2; i <= Math.sqrt(k); i++) { while (k % i == 0) { factors.push(i); k /= i; } } if (k > 1) factors.push(k); // Initialize the count of each // character position as 1 let count = new Array(n).fill(1); let index = 0; // Loop until the list // becomes empty while (factors.length > 0) { // Increase the character // count by multiplying it // with the prime factor count[index++] *= factors[factors.length - 1]; factors.pop(); // If we reach end then again // start from beginning if (index == n) index = 0; } // Store the output let s = new String(); for (i = 0; i < n; i++) { while (count[i]-- > 0) { s += str[i]; } } // Print the string document.write(s);}// Driver code// Given Stringlet str = "code";let k = 20;// Function CallprintSubsequenceString(str, k);// This code is contributed by _saurabh_jaiswal</script> |
Output:
cccccoodde
Time Complexity: O(N*log2(log2(N)))
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
