Dados tres enteros no negativos, X , Y y K , la tarea es encontrar la K- ésima string lexicográfica más pequeña que tenga X ocurrencias del carácter ‘a’ e Y ocurrencias del carácter ‘b’ .
Ejemplos:
Entrada: X = 2, Y = 3, K = 3
Salida: abbab
Explicación:
Primera string lexicográfica más pequeña = “aabbb”.
Segunda string lexicográfica más pequeña = “ababb”.
Tercera string lexicográfica más pequeña = “abbab”.Entrada: X = 4, Y = 3, K = 4
Salida: aaabbba
Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones distintas de la string X ocurrencias del carácter ‘a’ e Y ocurrencias del carácter ‘b’ . Luego, primero, ordene la array de strings de salida en orden lexicográfico e imprima la string de índice Kth .
Complejidad temporal: O(N*N!), donde N es (X + Y)
Espacio auxiliar: O(N!)
Enfoque eficiente: este problema tiene la propiedad de subproblemas superpuestos y la propiedad de subestructura óptima . Entonces este problema se puede resolver usando Programación Dinámica . Al igual que otros problemas típicos de programación dinámica (DP), se puede evitar volver a calcular los mismos subproblemas construyendo una array temporal que almacene los resultados de los subproblemas. Siga los pasos a continuación para resolver este problema.
- Inicialice una array 2D , dp[][] donde dp[i][j] denota el número de strings que contienen i número de a y j número de b .
- Iterar en el rango [0, X] usando la variable i :
- Iterar en el rango [0, Y] usando la variable j:
- Si i es mayor que 0, actualice dp[i][j] a dp[i][j] + dp[i-1][j] .
- Si j es mayor que 0 , actualice dp[i][j] a dp[i][j] + dp[i][j-1] .
- Iterar en el rango [0, Y] usando la variable j:
- Ahora, busque recursivamente la K-ésima string lexicográfica más pequeña llamando a la función kthString(int X, int Y, int K) .
- Manejar los casos base:
- Si solo hay caracteres ‘a’ presentes, devuelva una string de todos los caracteres ‘a’ .
- Si solo hay caracteres ‘b’ presentes, devuelve una string de todos los caracteres ‘b’ .
- Si hay más que o iguales a K strings que comienzan con ‘a’ , devuelva “a” + kthString(X-1, Y, K) .
- De lo contrario, el primer carácter de la string resultante es ‘b’ , devuelve “b” + kthString(X, Y-1, K – dp[X-1][Y]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 30;
// Function to fill dp array
void findNumString(int X, int Y, int dp[][MAX])
{
// Initialize all the entries with 0
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
dp[i][j] = 0;
}
}
// Update dp[0][0] to 1
dp[0][0] = 1;
// Traverse the dp array
for (int i = 0; i <= X; ++i) {
for (int j = 0; j <= Y; ++j) {
// Update the value of dp[i][j]
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Recursive function to find the Kth
// lexicographical smallest string
string kthString(int X, int Y, int K, int dp[][MAX])
{
// Handle the base cases
if (X == 0) {
return string(Y, 'b');
}
if (Y == 0) {
return string(X, 'a');
}
// If there are more than or equal
// to K strings which start with a,
// then the first character is 'a'
if (K <= dp[X - 1][Y]) {
return string("a") + kthString(X - 1, Y, K, dp);
}
// Otherwise the first character
// of the resultant string is 'b'
else {
return string("b")
+ kthString(X, Y - 1,
K - dp[X - 1][Y], dp);
}
}
// Function to find the Kth
// lexicographical smallest string
void kthStringUtil(int X, int Y, int K)
{
int dp[MAX][MAX];
// Function call to fill the dp array
findNumString(X, Y, dp);
// Print the resultant string
cout << kthString(X, Y, K, dp) << '\n';
}
// Driver Code
int main()
{
// Given Input
int X = 4;
int Y = 3;
int K = 4;
// Function Call
kthStringUtil(X, Y, K);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
static int MAX = 30;
// Function to fill dp array
static void findNumString(int X, int Y, int dp[][])
{
// Initialize all the entries with 0
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
dp[i][j] = 0;
}
}
// Update dp[0][0] to 1
dp[0][0] = 1;
// Traverse the dp array
for (int i = 0; i <= X; ++i) {
for (int j = 0; j <= Y; ++j) {
// Update the value of dp[i][j]
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Recursive function to find the Kth
// lexicographical smallest string
static String kthString(int X, int Y, int K, int dp[][])
{
// Handle the base cases
String x1 = "";
String y1 = "";
for (int i=0;i<Y;i++){
x1 += 'b';
}
for (int i=0;i<X;i++){
y1 += 'a';
}
if (X == 0)
return x1;
if (Y == 0)
return y1;
// If there are more than or equal
// to K strings which start with a,
// then the first character is 'a'
if (K <= dp[X - 1][Y]) {
return ("a" + kthString(X - 1, Y, K, dp));
}
// Otherwise the first character
// of the resultant string is 'b'
else {
return ("b" + kthString(X, Y - 1, K - dp[X - 1][Y], dp));
}
}
// Function to find the Kth
// lexicographical smallest string
static void kthStringUtil(int X, int Y, int K)
{
int dp[][] = new int [MAX][MAX];
// Function call to fill the dp array
findNumString(X, Y, dp);
// Print the resultant string
System.out.println(kthString(X, Y, K, dp));
}
// Driver Code
public static void main(String args[])
{
// Given Input
int X = 4;
int Y = 3;
int K = 4;
// Function Call
kthStringUtil(X, Y, K);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach from typing import Mapping MAX = 30 # Function to fill dp array def findNumString(X, Y, dp): # Initialize all the entries with 0 for i in range(0, MAX): for j in range(0, MAX): dp[i][j] = 0 # Update dp[0][0] to 1 dp[0][0] = 1 # Traverse the dp array for i in range(0, X + 1): for j in range(0, Y + 1): # Update the value of dp[i][j] if (i > 0): dp[i][j] += dp[i - 1][j] if (j > 0): dp[i][j] += dp[i][j - 1] # Recursive function to find the Kth # lexicographical smallest string def kthString(X, Y, K, dp): # Handle the base cases x1 = "" y1 = "" for i in range(0, Y): x1 += 'b' for i in range(0, X): y1 += 'a' if (X == 0): return x1 if (Y == 0): return y1 # If there are more than or equal # to K strings which start with a, # then the first character is 'a' if (K <= dp[X - 1][Y]): return "a" + kthString(X - 1, Y, K, dp) # Otherwise the first character # of the resultant string is 'b' else: return "b" + kthString(X, Y - 1, K - dp[X - 1][Y], dp) # Function to find the Kth # lexicographical smallest string def kthStringUtil(X, Y, K): dp = [[0 for i in range(MAX)] for col in range(MAX)] # Function call to fill the dp array findNumString(X, Y, dp) # Print the resultant print(kthString(X, Y, K, dp)) # Driver Code # Given Input X = 4 Y = 3 K = 4 # Function Call kthStringUtil(X, Y, K) # This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG{
static int MAX = 30;
// Function to fill dp array
static void findNumString(int X, int Y, int[,] dp)
{
// Initialize all the entries with 0
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
dp[i, j] = 0;
}
}
// Update dp[0][0] to 1
dp[0, 0] = 1;
// Traverse the dp array
for (int i = 0; i <= X; ++i) {
for (int j = 0; j <= Y; ++j) {
// Update the value of dp[i][j]
if (i > 0) {
dp[i, j] += dp[i - 1, j];
}
if (j > 0) {
dp[i, j] += dp[i, j - 1];
}
}
}
}
// Recursive function to find the Kth
// lexicographical smallest string
static string kthString(int X, int Y, int K, int[,] dp)
{
// Handle the base cases
string x1 = "";
string y1 = "";
for (int i=0;i<Y;i++){
x1 += 'b';
}
for (int i=0;i<X;i++){
y1 += 'a';
}
if (X == 0)
return x1;
if (Y == 0)
return y1;
// If there are more than or equal
// to K strings which start with a,
// then the first character is 'a'
if (K <= dp[X - 1, Y]) {
return ("a" + kthString(X - 1, Y, K, dp));
}
// Otherwise the first character
// of the resultant string is 'b'
else {
return ("b" + kthString(X, Y - 1, K - dp[X - 1, Y], dp));
}
}
// Function to find the Kth
// lexicographical smallest string
static void kthStringUtil(int X, int Y, int K)
{
int[,] dp = new int [MAX, MAX];
// Function call to fill the dp array
findNumString(X, Y, dp);
// Print the resultant string
Console.WriteLine(kthString(X, Y, K, dp));
}
// Driver code
static void Main()
{
// Given Input
int X = 4;
int Y = 3;
int K = 4;
// Function Call
kthStringUtil(X, Y, K);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
const MAX = 30
// Function to fill dp array
function findNumString(X, Y, dp){
// Initialize all the entries with 0
for(let i = 0; i < MAX; i++)
for(let j = 0; j < MAX; j++)
dp[i][j] = 0
// Update dp[0][0] to 1
dp[0][0] = 1
// Traverse the dp array
for(let i = 0; i < X + 1; i++)
{
for(let j = 0; j < Y + 1; j++)
{
// Update the value of dp[i][j]
if (i > 0)
dp[i][j] += dp[i - 1][j]
if (j > 0)
dp[i][j] += dp[i][j - 1]
}
}
}
// Recursive function to find the Kth
// lexicographical smallest string
function kthString(X, Y, K, dp){
// Handle the base cases
let x1 = ""
let y1 = ""
for(let i = 0; i < Y; i++)
x1 += 'b'
for(let i = 0; i < X; i++)
y1 += 'a'
if (X == 0)
return x1
if (Y == 0)
return y1
// If there are more than or equal
// to K strings which start with a,
// then the first character is 'a'
if (K <= dp[X - 1][Y])
return "a" + kthString(X - 1, Y, K, dp)
// Otherwise the first character
// of the resultant string is 'b'
else
return "b" + kthString(X, Y - 1,
K - dp[X - 1][Y], dp)
}
// Function to find the Kth
// lexicographical smallest string
function kthStringUtil(X, Y, K)
{
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAX);
}
// Function call to fill the dp array
findNumString(X, Y, dp)
// Print the resultant
document.write(kthString(X, Y, K, dp),"</br>")
}
// Driver Code
// Given Input
let X = 4
let Y = 3
let K = 4
// Function Call
kthStringUtil(X, Y, K)
// This code is contributed by shinjanpatra
</script>
Producción:
aaabbba
Complejidad temporal: O(X*Y)
Espacio auxiliar: O(X*Y)
Enfoque eficiente: el enfoque anterior se puede optimizar aún más mediante la implementación iterativa de la función KthString . Siga los pasos a continuación para resolver este problema:
- Declare una array 2D , dp donde dp[i][j] denota el número de strings que contienen i número de a y j número de b .
- Iterar en el rango [0, X] usando la variable i :
- Iterar en el rango [0, Y] usando la variable j:
- Si i es mayor que 0, actualice dp[i][j] a dp[i][j] + dp[i-1][j].
- Si j es mayor que 0 , actualice dp[i][j] a dp[i][j] + dp[i][j-1].
- Iterar en el rango [0, Y] usando la variable j:
- Ahora, encuentre iterativamente la K-ésima string lexicográfica más pequeña.
- Traverse mientras X es mayor que 0 e Y es mayor que 0 :
- Si hay más que o iguales a K strings que comienzan con ‘a’ , imprima ‘a’ y disminuya X en 1 .
- De lo contrario, el primer carácter de la string resultante es ‘b’ , imprima ‘b’ y disminuya Y en 1 .
- Si solo hay caracteres ‘ a’ presentes, imprima una string de todos los caracteres ‘ a ‘.
- Si solo hay caracteres ‘ b ‘ presentes, imprima una string de todos los caracteres ‘ b ‘.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 30;
// Function to fill dp array
void findNumString(int X, int Y, int dp[][MAX])
{
// Initialize all the entries with 0
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
dp[i][j] = 0;
}
}
// Update dp[0][0] to 1
dp[0][0] = 1;
// Traverse the dp array
for (int i = 0; i <= X; ++i) {
for (int j = 0; j <= Y; ++j) {
// Update the value of dp[i][j]
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Iterative function to find the Kth
// lexicographical smallest string
void kthString(int X, int Y, int K, int dp[][MAX])
{
while (X > 0 and Y > 0) {
// If there are more than or
// equal to K strings which start
// with a, then print 'a'
if (K <= dp[X - 1][Y]) {
cout << 'a';
X -= 1;
}
// Otherwise the first character
// of the resultant string is b
else {
K -= dp[X - 1][Y];
cout << 'b';
Y -= 1;
}
}
// If there are only 'a' characters
// present then print a string of
// all 'a' characters
cout << string(X, 'a');
// If there are only 'b' characters
// present then print a string of
// all 'b' characters
cout << string(Y, 'b');
cout << '\n';
}
// Function to find the Kth
// lexicographical smallest string
void kthStringUtil(int X, int Y, int K)
{
int dp[MAX][MAX];
// Function call to fill the dp array
findNumString(X, Y, dp);
// Function call to find the
// required string
kthString(X, Y, K, dp);
}
// Driver Code
int main()
{
// Given Input
int X = 4;
int Y = 3;
int K = 4;
// Function Call
kthStringUtil(X, Y, K);
return 0;
}
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 30;
// Function to fill dp array
static void findNumString(int X, int Y, int[][] dp)
{
// Initialize all the entries with 0
for (int i = 0 ; i < MAX ; i++) {
for (int j = 0 ; j < MAX ; j++) {
dp[i][j] = 0;
}
}
// Update dp[0][0] to 1
dp[0][0] = 1;
// Traverse the dp array
for (int i = 0 ; i <= X ; ++i) {
for (int j = 0 ; j <= Y ; ++j) {
// Update the value of dp[i][j]
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
// Iterative function to find the Kth
// lexicographical smallest string
static void kthString(int X, int Y, int K, int[][] dp)
{
while (X > 0 && Y > 0) {
// If there are more than or
// equal to K strings which start
// with a, then print 'a'
if (K <= dp[X - 1][Y]) {
Console.Write('a');
X -= 1;
}
// Otherwise the first character
// of the resultant string is b
else {
K -= dp[X - 1][Y];
Console.Write('b');
Y -= 1;
}
}
// If there are only 'a' characters
// present then print a string of
// all 'a' characters
String ans = "";
for(int i = 0 ; i < X ; i++){
ans+="a";
}
Console.Write(ans);
ans = "";
// If there are only 'b' characters
// present then print a string of
// all 'b' characters
for(int i = 0 ; i < Y ; i++){
ans+="b";
}
Console.Write(ans);
Console.Write("\n");
}
// Function to find the Kth
// lexicographical smallest string
static void kthStringUtil(int X, int Y, int K)
{
int[][] dp = new int[MAX][];
for(int i = 0 ; i < MAX ; i++){
dp[i] = new int[MAX];
}
// Function call to fill the dp array
findNumString(X, Y, dp);
// Function call to find the
// required string
kthString(X, Y, K, dp);
}
// Driver Code
public static void Main(string[] args){
// Given Input
int X = 4;
int Y = 3;
int K = 4;
// Function Call
kthStringUtil(X, Y, K);
}
}
// This code is contributed by subhamgoyal2014.
Producción:
aaabbba
Complejidad temporal: O(X*Y)
Espacio auxiliar: O(X*Y)
Publicación traducida automáticamente
Artículo escrito por siddhantdugar241 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA