Dada una string S que consta solo de letras minúsculas, la tarea es encontrar la string lexicográficamente más grande que se puede obtener eliminando K caracteres de la string dada.
Ejemplos:
Entrada: s = “zyxedcba”, K=1
Salida: zyxedcb
Explicación: El carácter con el valor ASCII más pequeño de la string dada es ‘a’.
La eliminación de ‘a’ genera la string lexicográficamente más grande posible.Entrada: s = “abcde”, K=2
Salida: cde
Enfoque:
La idea es usar Stack Data Structure para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Atraviesa la cuerda.
- Para cada carácter, compruebe si es mayor que el carácter en la parte superior de la pila . Si se determina que es cierto, extrae el elemento superior de la pila si K > 0 .
- Inserta el personaje en la pila.
- Después de completar el recorrido de la string, si K > 0 , elimine los elementos K superiores de la pila.
- Finalmente, almacene los caracteres en la pila como la respuesta. Imprime la respuesta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> using namespace std; string largestString(string num, int k) { // final result string string ans = ""; for (auto i : num) { // If the current char exceeds the // character at the top of the stack while (ans.length() && ans.back() < i && k > 0) { // Remove from the end of the string ans.pop_back(); // Decrease k for the removal k--; } // Insert current character ans.push_back(i); } // Perform remaining K deletions // from the end of the string while (ans.length() and k--) { ans.pop_back(); } // Return the string return ans; } // Driver Code int main() { string str = "zyxedcba"; int k = 1; cout << largestString(str, k) << endl; }
Java
// Java program to implement the // above approach class GFG{ static String largestString(String num, int k) { // Final result String String ans = ""; for(char i : num.toCharArray()) { // If the current char exceeds the // character at the top of the stack while (ans.length() > 0 && ans.charAt(ans.length() - 1) < i && k > 0) { // Remove from the end of the String ans = ans.substring(0, ans.length() - 1); // Decrease k for the removal k--; } // Insert current character ans += i; } // Perform remaining K deletions // from the end of the String while (ans.length() > 0 && k-- > 0) { ans = ans.substring(0, ans.length() - 1); } // Return the String return ans; } // Driver Code public static void main(String[] args) { String str = "zyxedcba"; int k = 1; System.out.print(largestString(str, k) + "\n"); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to implement the # above approach def largestString(num, k): # Final result string ans = [] for i in range(len(num)): # If the current char exceeds the # character at the top of the stack while(len(ans) and ans[-1] < num[i] and k > 0): # Remove from the end of the string ans.pop() # Decrease k for the removal k -= 1 # Insert current character ans.append(num[i]) # Perform remaining K deletions # from the end of the string while(len(ans) and k): k -= 1 ans.pop() # Return the string return ans # Driver code str = "zyxedcba" k = 1 print(*largestString(str, k), sep = "") # This code is contributed by divyeshrabadiya07
C#
// C# program to implement the // above approach using System; class GFG{ static String largestString(String num, int k) { // Final result String String ans = ""; foreach(char i in num.ToCharArray()) { // If the current char exceeds the // character at the top of the stack while (ans.Length > 0 && ans[ans.Length - 1] < i && k > 0) { // Remove from the end of the String ans = ans.Substring(0, ans.Length - 1); // Decrease k for the removal k--; } // Insert current character ans += i; } // Perform remaining K deletions // from the end of the String while (ans.Length > 0 && k-- > 0) { ans = ans.Substring(0, ans.Length - 1); } // Return the String return ans; } // Driver Code public static void Main(String[] args) { String str = "zyxedcba"; int k = 1; Console.Write(largestString(str, k) + "\n"); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to implement the // above approach function largestString(num, k) { // Final result String var ans = ""; var str = num.split(""); for (const i of str) { // If the current char exceeds the // character at the top of the stack while (ans.length > 0 && ans[ans.length - 1] < i && k > 0) { // Remove from the end of the String ans = ans.substring(0, ans.length - 1); // Decrease k for the removal k--; } // Insert current character ans += i; } // Perform remaining K deletions // from the end of the String while (ans.length > 0 && k-- > 0) { ans = ans.substring(0, ans.length - 1); } // Return the String return ans; } // Driver Code var str = "zyxedcba"; var k = 1; document.write(largestString(str, k) + "<br>"); </script>
zyxedcb
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por red_devil09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA