String lexicográficamente más pequeña formada al agregar un carácter de los primeros K caracteres de una string | conjunto 2

Dada una string str que consiste en letras minúsculas y un número entero K , puede realizar las siguientes operaciones en str

1. Inicialice una string vacía X = «» .
2. Tome cualquier carácter de los primeros K caracteres de str y agréguelo a X .
3. Elimina el carácter elegido de str .
4. Repita los pasos anteriores mientras queden caracteres en str.

La tarea es generar X de modo que sea lexicográficamente lo más pequeño posible y luego imprimir la string generada. Ejemplos:

Entrada: str = “geek”, K = 2 Salida: eegk Operación 1: str = “gek”, X = “e” Operación 2: str = “gk”, X = “ee” Operación 3: str = “k” , X = “eeg” Operación 4: str = “”, X = “eegk” Entrada: str = “geeksforgeeks”, K = 5 Salida: eefggeekkorss

Enfoque: para obtener la string lexicográficamente más pequeña, debemos tomar el carácter mínimo de los primeros K caracteres cada vez que elegimos un carácter de str . Para hacer eso, podemos poner los primeros K caracteres en una cola de prioridad (min-heap) y luego elegir el carácter más pequeño y agregarlo a X. Luego, empuje el siguiente carácter en str a la cola de prioridad y repita el proceso hasta que queden caracteres para procesar. A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the lexicographically
// smallest required string
string getSmallestStr(string S, int K)
{
 
    // Initially empty string
    string X = "";
 
    // min heap of characters
    priority_queue<char, vector<char>, greater<char> > pq;
 
    // Length of the string
    int i, n = S.length();
 
    // K cannot be greater than
    // the size of the string
    K = min(K, n);
 
    // First push the first K characters
    // into the priority_queue
    for (i = 0; i < K; i++)
        pq.push(S[i]);
 
    // While there are characters to append
    while (!pq.empty()) {
 
        // Append the top of priority_queue to X
        X += pq.top();
 
        // Remove the top element
        pq.pop();
 
        // Push only if i is less than
        // the size of string
        if (i < S.length())
            pq.push(S[i]);
 
        i++;
    }
 
    // Return the generated string
    return X;
}
 
// Driver code
int main()
{
    string S = "geeksforgeeks";
    int K = 5;
 
    cout << getSmallestStr(S, K);
 
    return 0;
}

// Java implementation of the approach
import java.util.PriorityQueue;
 
class GFG
{
 
    // Function to return the lexicographically
    // smallest required string
    static String getSmallestStr(String S, int K)
    {
 
        // Initially empty string
        String X = "";
 
        // min heap of characters
        PriorityQueue<Character> pq = new PriorityQueue<>();
 
        // Length of the string
        int i, n = S.length();
 
        // K cannot be greater than
        // the size of the string
        K = Math.min(K, n);
 
        // First push the first K characters
        // into the priority_queue
        for (i = 0; i < K; i++)
            pq.add(S.charAt(i));
 
        // While there are characters to append
        while (!pq.isEmpty())
        {
 
            // Append the top of priority_queue to X
            X += pq.peek();
 
            // Remove the top element
            pq.remove();
 
            // Push only if i is less than
            // the size of string
            if (i < S.length())
                pq.add(S.charAt(i));
                 
            i++;
        }
 
        // Return the generated string
        return X;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "geeksforgeeks";
        int K = 5;
        System.out.println(getSmallestStr(S, K));
    }
}
 
// This code is contributed by
// sanjeev2552

eefggeekkorss

Complejidad de tiempo: O(nlogn) donde n es la longitud de la string.
Espacio auxiliar: O(K), ya que se usa espacio extra de tamaño K para construir la cola de prioridad