Lexicográficamente, la K-ésima string más pequeña que tiene ‘a’ X veces y ‘b’ Y veces

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] .
  • 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].
  • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *