Dada una string str que consiste en letras minúsculas y un número entero K , puede realizar las siguientes operaciones en str
- Inicialice una string vacía X = «» .
- Tome cualquier carácter de los primeros K caracteres de str y agréguelo a X .
- Elimina el carácter elegido de str .
- 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++
// 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
// 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
Publicación traducida automáticamente
Artículo escrito por MandeepSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA