Dada una string S de longitud N , que consta de alfabetos en minúsculas, la tarea es encontrar la string lexicográficamente más larga que se puede obtener reemplazando como máximo K caracteres de la string dada.
Ejemplos:
Entrada: S = “dbza”, K = 1
Salida: zbza
Explicación: Reemplace S[0] (= ‘d’) con ‘z’ para obtener la string lexicográficamente más grande.Entrada: S = “zzzz”, K = 2
Salida: zzzz
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es recorrer la array de izquierda a derecha y reemplazar todos los caracteres que no sean z con z . Siga los pasos a continuación para resolver el problema:
- Ejecute un ciclo para i = 0 a la longitud de la string:
- Si el carácter actual no es igual a z y K no es igual a 0:
- Luego, reemplace el carácter actual con z .
- K = K – 1.
- Si el carácter actual no es igual a z y K no es igual a 0:
- Finalmente, devuelva la string modificada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; string largestString(string s, int k) { // Traverse each element of the string for (int i = 0; i < s.size(); i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s[i] = 'z'; k--; } } // Return the modified string return s; } // Driver code int main() { string s = "dbza"; int k = 1; cout << largestString(s, k) << endl; return 0; }
Java
// Java implementation of the above approach class GFG{ static String largestString(String s, int k) { // Traverse each element of the string for(int i = 0; i < s.length(); i++) { // If the current character // can be replaced with 'z' if (s.charAt(i) != 'z' && k > 0) { s = s.replace(s.charAt(i),'z'); k--; } } // Return the modified string return s; } // Driver code public static void main(String args[]) { String s = "dbza"; int k = 1; System.out.println(largestString(s, k)); } } // This code is contributed by SoumikMondal
Python3
# Python3 implementation of # the above approach def largestString(s, k): # Traverse each element of the string for i in range(len(s)): # If the current character # can be replaced with 'z' if (s[i] != 'z' and k > 0): s[i] = 'z' k -= 1 # Return the modified string return "".join(s) # Driver code if __name__ == '__main__': s = "dbza" k = 1 print (largestString([i for i in s], k)) # This code is contributed by mohit kumar 29
C#
// C# implementation of // the above approach using System; using System.Collections.Generic; class GFG{ static string largestString(string s, int k) { // Traverse each element of the string for(int i = 0; i < s.Length; i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s = s.Replace(s[i],'z'); k--; } } // Return the modified string return s; } // Driver code public static void Main() { string s = "dbza"; int k = 1; Console.Write(largestString(s, k)); } } // This code is contributed by SURENDRA_GANGWAR
Javascript
<script> // JavaScript implementation of // the above approach function largestString(s, k) { // Traverse each element of the string for (let i = 0; i < s.length; i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s = s.substring(0, i) + 'z' + s.substring(i + 1); k--; } } // Return the modified string return s; } // Driver code var s = "dbza"; var k = 1; document.write(largestString(s, k)); // This code is contributed by Potta Lokesh </script>
zbza
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA