Encuentre la string k-ésima en orden lexicográfico que consta de n-2 X y 2 Y

Dados dos números N y K , la tarea es encontrar la K ^-ésima string en orden lexicográfico si la string inicial contiene (N-2) x primero y luego 2 Y.
Nota: 
 

1 ≤ K ≤ N*(N-1)/2, N*(N-1)/2 son el número de permutaciones posibles 
 

Ejemplos: 
 

Entrada: N = 5, K = 7 
Salida: YXXXY 
Las strings posibles en orden lexicográfico 
1. XXXYY 
2. XXYXY 
3. XXYYX 
4. XYXXY 
5. XYXYX 
6. XYYXX 
7. YXXXY 
8. YXXYX 
9. YXYXX 
10. YYXXX
Entrada: N = 8, K = 20 
Salida: XYXYXXXX 
 

Enfoque : 
Para encontrar la string de la k ^-ésima posición, tenemos que seguir los siguientes pasos: 
 

1. tenemos que encontrar la posición de la aparición más a la izquierda de ‘Y’ iterando sobre todas las posiciones desde n-2 hasta 0 .
2. Ahora, mientras se itera, si k<=ni-1 entonces esta es la posición requerida de la aparición más a la izquierda de ‘Y’ y la posición de la aparición más a la derecha es nk para que podamos imprimir la respuesta.
3. De lo contrario, reduzcamos k por ni-1 , es decir, eliminemos todas las strings que tengan la ‘Y’ más a la izquierda en la posición actual y procedamos a la siguiente posición. De esta forma consideramos todas las strings posibles en orden lexicográfico.

A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program find the Kth string in
// lexicographical order consisting
// of N-2 x’s and 2 y’s
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth string
// in lexicographical order which
// consists of N-2 x’s and 2 y’s
void kth_string(int n, int k)
{
    // Iterate for all possible positions of
    // Left most Y
    for (int i = n - 2; i >= 0; i--) {
        // If i is the left most position of Y
        if (k <= (n - i - 1)) {
            // Put Y in their positions
            for (int j = 0; j < n; j++) {
                if (j == i or j == n - k)
                    cout << 'Y';
                else
                    cout << 'X';
            }
 
            break;
        }
        k -= (n - i - 1);
    }
}
 
// Driver code
int main()
{
    int n = 5, k = 7;
 
    // Function call
    kth_string(n, k);
 
    return 0;
}

// Java program find the Kth String in
// lexicographical order consisting
// of N-2 x’s and 2 y’s
class GFG{
 
// Function to find the Kth String
// in lexicographical order which
// consists of N-2 x’s and 2 y’s
static void kth_String(int n, int k)
{
     
    // Iterate for all possible
    // positions of eft most Y
    for(int i = n - 2; i >= 0; i--)
    {
       // If i is the left
       // most position of Y
       if (k <= (n - i - 1))
       {
           // Put Y in their positions
           for(int j = 0; j < n; j++)
           {
              if (j == i || j == n - k)
                  System.out.print('Y');
              else
                  System.out.print('X');
           }
 
            break;
        }
         
        k -= (n - i - 1);
    }
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5, k = 7;
 
    // Function call
    kth_String(n, k);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program find the Kth string in
# lexicographical order consisting
# of N-2 x’s and 2 y’s
 
# Function to find the Kth string
# in lexicographical order which
# consists of N-2 x’s and 2 y’s
def kth_string(n, k):
 
    # Iterate for all possible positions of
    # left most Y
    for i in range(n - 2, -1, -1):
         
        # If i is the left most position of Y
        if k <= (n - i - 1):
             
            # Put Y in their positions
            for j in range(n):
                if (j == i or j == n - k):
                    print('Y', end = "")
                else:
                    print('X', end = "")
            break
 
        k -= (n - i - 1)
 
# Driver code
n = 5
k = 7
 
# Function call
kth_string(n, k)
 
# This code is contributed by divyamohan123

// C# program find the Kth String in
// lexicographical order consisting
// of N-2 x’s and 2 y’s
using System;
 
class GFG{
 
// Function to find the Kth String
// in lexicographical order which
// consists of N-2 x’s and 2 y’s
static void kth_String(int n, int k)
{
     
    // Iterate for all possible
    // positions of eft most Y
    for(int i = n - 2; i >= 0; i--)
    {
         
       // If i is the left
       // most position of Y
       if (k <= (n - i - 1))
       {
            
           // Put Y in their positions
           for(int j = 0; j < n; j++)
           {
               if (j == i || j == n - k)
                   Console.Write('Y');
               else
                   Console.Write('X');
           }
           break;
       }
       k -= (n - i - 1);
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 5, k = 7;
 
    // Function call
    kth_String(n, k);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// javascript program find the Kth String in
// lexicographical order consisting
// of N-2 x’s and 2 y’s
 
// Function to find the Kth String
// in lexicographical order which
// consists of N-2 x’s and 2 y’s
function kth_String(n , k)
{
     
    // Iterate for all possible
    // positions of eft most Y
    for(i = n - 2; i >= 0; i--)
    {
       // If i is the left
       // most position of Y
       if (k <= (n - i - 1))
       {
           // Put Y in their positions
           for(j = 0; j < n; j++)
           {
              if (j == i || j == n - k)
                  document.write('Y');
              else
                  document.write('X');
           }
            break;
        }   
        k -= (n - i - 1);
    }
}
 
// Driver code
var n = 5, k = 7;
 
// Function call
kth_String(n, k);
 
// This code is contributed by Amit Katiyar
</script>

YXXXY

Complejidad de tiempo: O(N ² ) // se utilizan dos bucles anidados uno dentro del otro, por lo que la complejidad es n*n

Espacio auxiliar: O (1) // no se usa una array adicional, por lo que el espacio es constante