Dada una string S de N caracteres, la tarea es encontrar la string lexicográfica más pequeña después de realizar cada una de las siguientes operaciones N veces en cualquier orden:
- Elimine el primer carácter de S e insértelo en una pila X .
- Retire la parte superior de la pila X y agréguela al final de otra string Y que inicialmente está vacía.
Ejemplo:
Entrada: S = “cab”
Salida: abc
Explicación: La string dada se puede obtener usando las siguientes operaciones:
- Realice la operación 1. Por lo tanto, S = «ab», X = «c», Y = «».
- Realice la operación 1. Por lo tanto, S = «b», X = «ca», Y = «».
- Realice la operación 2. Por lo tanto, S = «b», X = «c», Y = «a».
- Realice la operación 1. Por lo tanto, S = «», X = «cb», Y = «a».
- Realice la operación 2. Por lo tanto, S = “”, X = “c”, Y = “ab”.
- Realice la operación 2. Por lo tanto, S = “”, X = “”, Y = “abc”.
Ahora, cada una de las operaciones dadas se realiza N veces y la string obtenida es «abc», que es la más pequeña posible.
Entrada: S = “acdb”
Salida: abdc
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es realizar la primera operación hasta que la parte superior de la pila contenga el carácter más pequeño después del cual se puede agregar a la string Y . Esto se puede hacer de manera eficiente manteniendo una array de sufijos, donde sufijo[i] almacena el valor ASCII más pequeño del sufijo hasta el i -ésimo carácter. A continuación se detallan los pasos a seguir:
- Recorra la string y cree una array de sufijos suff[] según sea necesario.
- Si la pila X no está vacía y suff[i] es mayor que el carácter superior de la pila X , extraiga el carácter superior de la pila X y agréguelo a la string Y.
- De lo contrario, si suff[i] es igual a S[i], agregue a la string Y .
- De lo contrario, inserte el carácter S[i] en la pila X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find lexicographical smallest // string by performing the given operations string smallestString(string S) { // Stores the size of S int N = S.size(); // Suffix Array int suff[N + 1]; // Initial Condition suff[N] = INT_MAX; // Loop to calculate suffix array for (int i = N - 1; i >= 0; i--) { suff[i] = min(suff[i + 1], (int)S[i]); } // Initialize the stack X // and string y as empty stack<char> X; string Y = ""; // Loop to traverse string for (int i = 0; i < N; i++) { // If X is not empty and suff[i] // is greater than equal to top // character of stack X if (X.size() > 0 && suff[i] >= X.top()) { Y += X.top(); X.pop(); i--; } // If suff[i] is equal to S[i] else if (suff[i] == S[i]) { Y += S[i]; } // Otherwise push character // S[i] into the stack X else { X.push(S[i]); } } // Append all remaining characters // of X into string Y while (X.size() > 0) { Y += X.top(); X.pop(); } // Return Answer return Y; } // Driver Code int main() { string s = "acdb"; cout << smallestString(s); return 0; }
Java
// Java program of the above approach import java.util.*; class GFG { // Function to find lexicographical smallest // string by performing the given operations public static String smallestString(String S) { // Stores the size of S int N = S.length(); // Suffix Array int[] suff = new int[N + 1]; // Initial Condition suff[N] = Integer.MAX_VALUE; // Loop to calculate suffix array for (int i = N - 1; i >= 0; i--) { suff[i] = Math.min(suff[i + 1], (int)S.charAt(i)); } // Initialize the stack X // and string y as empty Stack<Character> X = new Stack<Character>(); String Y = ""; // Loop to traverse string for (int i = 0; i < N; i++) { // If X is not empty and suff[i] // is greater than equal to top // character of stack X if (X.size() > 0 && suff[i] >= X.peek()) { Y += X.peek(); X.pop(); i--; } // If suff[i] is equal to S[i] else if (suff[i] == S.charAt(i)) { Y += S.charAt(i); } // Otherwise push character // S[i] into the stack X else { X.push(S.charAt(i)); } } // Append all remaining characters // of X into string Y while (X.size() > 0) { Y += X.peek(); X.pop(); } // Return Answer return Y; } // Driver Code public static void main(String[] args) { String s = "acdb"; System.out.print(smallestString(s)); } } // This code is contributed by Taranpreet
Python3
# Python program of the above approach import sys # Function to find lexicographical smallest # string by performing the given operations def smallestString(S): # Stores the size of S N = len(S) # Suffix Array suff = [0]*(N+1) # Initial Condition suff[N] = sys.maxsize # Loop to calculate suffix array for i in range(N - 1, -2, -1): suff[i] = min(suff[i + 1], ord(S[i])) # Initialize the stack X # and string y as empty X = [] Y = "" # Loop to traverse string for i in range(0, N): # If X is not empty and suff[i] # is greater than equal to top # character of stack X if (len(X) > 0 and suff[i] >= ord(X[-1])): Y = Y + X[-1] X.pop() i = i - 1 # If suff[i] is equal to S[i] elif (suff[i] == ord(S[i])): Y = Y + S[i] # Otherwise push character # S[i] into the stack X else: X.append(S[i]) # Append all remaining characters # of X into string Y while (len(X) > 0): Y = Y + X[-1] X.pop() # Return Answer return Y # Driver Code s = "acdb" print(smallestString(s)) # This code is contributed by Taranpreet
C#
// C# program of the above approach using System; using System.Collections.Generic; class GFG { // Function to find lexicographical smallest // string by performing the given operations public static String smallestString(String S) { // Stores the size of S int N = S.Length; // Suffix Array int[] suff = new int[N + 1]; // Initial Condition suff[N] = int.MaxValue; // Loop to calculate suffix array for (int i = N - 1; i >= 0; i--) { suff[i] = Math.Min(suff[i + 1], (int)S[i]); } // Initialize the stack X // and string y as empty Stack<char> X = new Stack<char>(); String Y = ""; // Loop to traverse string for (int i = 0; i < N; i++) { // If X is not empty and suff[i] // is greater than equal to top // character of stack X if (X.Count > 0 && suff[i] >= X.Peek()) { Y += X.Peek(); X.Pop(); i--; } // If suff[i] is equal to S[i] else if (suff[i] == S[i]) { Y += S[i]; } // Otherwise push character // S[i] into the stack X else { X.Push(S[i]); } } // Append all remaining characters // of X into string Y while (X.Count > 0) { Y += X.Peek(); X.Pop(); } // Return Answer return Y; } // Driver Code public static void Main() { String s = "acdb"; Console.Write(smallestString(s)); } } // This code is contributed by Saurabh Jaiswal
Javascript
<script> // JavaScript code for the above approach // Function to find lexicographical smallest // string by performing the given operations function smallestString(S) { // Stores the size of S let N = S.length; // Suffix Array let suff = new Array(N + 1); // Initial Condition suff[N] = Number.MAX_VALUE; // Loop to calculate suffix array for (let i = N - 1; i >= 0; i--) { suff[i] = Math.min(suff[i + 1], S[i].charCodeAt(0)); } // Initialize the stack X // and string y as empty let X = []; let Y = ""; // Loop to traverse string for (let i = 0; i < N; i++) { // If X is not empty and suff[i] // is greater than equal to top // character of stack X if (X.length > 0 && suff[i] >= X[X.length - 1].charCodeAt(0)) { Y += X[X.length - 1]; X.pop(); i--; } // If suff[i] is equal to S[i] else if (String.fromCharCode(suff[i]) == S[i]) { Y += S[i]; } // Otherwise push character // S[i] into the stack X else { X.push(S[i]); } } // Append all remaining characters // of X into string Y while (X.length > 0) { Y += X[X.length - 1]; X.pop(); } // Return Answer return Y; } // Driver Code let s = "acdb"; document.write(smallestString(s)); // This code is contributed by Potta Lokesh </script>
abdc
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA