Dada una string str y un entero K , la tarea es encontrar una string S tal que tenga exactamente K subsecuencias de la string str dada .
Ejemplos:
Entrada: str = “gfg”, K = 10
Salida: gggggffg
Explicación:
Hay 10 subsecuencias posibles de la string dada “gggggffg”. Ellos son:
1. g gggg f f g
2. g g ggg f f g
3. gg g gg f f g
4. ggg g g f f g
5. gggg gf f g
6. g ggggf fg
7. g g gggf fg
8. gg g ggf fg
9. ggg ggf fg 10.
gggg gf fg .
Entrada: str = “código”, K = 20
Salida: cccccoodde
Explicación:
Hay 20 subsecuencias posibles de la string “ccccoodde”.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos seguir los pasos que se detallan a continuación:
- La idea es encontrar los factores primos de K y almacenar los factores primos (por ejemplo , factores ).
- Cree un conteo de array vacío del tamaño de la string dada para almacenar el conteo de cada carácter en la string resultante s . Inicialice la array con 1.
- Ahora extraiga elementos de la lista de factores y multiplíquelos a cada posición de la array de forma cíclica hasta que la lista quede vacía. Finalmente, tenemos el conteo de cada carácter de str en la array.
- Iterar en la array count[] y agregar el número de caracteres para cada carácter ch a la string resultante s .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function that computes the string s
void 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 code
int 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 approach import math # Function that computes # the string s def 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 code if __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 s
function 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 String
let str = "code";
let k = 20;
// Function Call
printSubsequenceString(str, k);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
cccccoodde
Complejidad de tiempo: O(N*log 2 (log 2 (N)))
Espacio auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por Ganeshchowdharysadanala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA