Encuentre el número más grande que se puede formar cambiando como máximo K dígitos

Dada la string str que representa un número y un entero K , la tarea es encontrar el número más grande que se puede formar cambiando como máximo K dígitos en el número dado.

Ejemplos: 

Entrada: str = “569431”, K = 3 
Salida: 999931 
Reemplace el primer, segundo y cuarto dígito con 9.
Entrada: str = “5687”, K = 2 
Salida: 9987  

Enfoque: para obtener el máximo número posible, los dígitos más a la izquierda deben reemplazarse con 9s. Para cada dígito del número a partir del dígito más a la izquierda, si aún no es 9 y K es mayor que 0, reemplácelo con 9 y disminuya K en 1. Repita estos pasos para cada dígito mientras K sea mayor que 0. Finalmente, imprimir el número actualizado.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the maximum number
// that can be formed by changing
// at most k digits in str
string findMaximumNum(string str, int n, int k)
{
 
    // For every digit of the number
    for (int i = 0; i < n; i++) {
 
        // If no more digits can be replaced
        if (k < 1)
            break;
 
        // If current digit is not already 9
        if (str[i] != '9') {
 
            // Replace it with 9
            str[i] = '9';
 
            // One digit has been used
            k--;
        }
    }
 
    return str;
}
 
// Driver code
int main()
{
    string str = "569431";
    int n = str.length();
    int k = 3;
 
    cout << findMaximumNum(str, n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
    // Function to return the maximum number
    // that can be formed by changing
    // at most k digits in str
    static StringBuilder findMaximumNum(StringBuilder str,
                                             int n, int k)
    {
     
        // For every digit of the number
        for (int i = 0; i < n; i++)
        {
     
            // If no more digits can be replaced
            if (k < 1)
                break;
     
            // If current digit is not already 9
            if (str.charAt(i) != '9')
            {
     
                // Replace it with 9
                str.setCharAt(i, '9');
     
                // One digit has been used
                k--;
            }
        }
        return str;
    }
     
    // Driver code
    public static void main (String [] args)
    {
        StringBuilder str = new StringBuilder("569431");
         
        int n = str.length();
        int k = 3;
     
        System.out.println(findMaximumNum(str, n, k));
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Function to return the maximum number
# that can be formed by changing
# at most k digits in str
def findMaximumNum(st, n, k):
 
    # For every digit of the number
    for i in range(n):
 
        # If no more digits can be replaced
        if (k < 1):
            break
 
        # If current digit is not already 9
        if (st[i] != '9'):
 
            # Replace it with 9
            st = st[0:i] + '9' + st[i + 1:]
 
            # One digit has been used
            k -= 1
 
    return st
 
# Driver code
st = "569431"
n = len(st)
k = 3
print(findMaximumNum(st, n, k))
 
# This code is contributed by
# divyamohan123

// C# implementation of the approach
using System;
using System.Text;
 
class GFG
{
    // Function to return the maximum number
    // that can be formed by changing
    // at most k digits in str
    static StringBuilder findMaximumNum(StringBuilder str,
                                        int n, int k)
    {
     
        // For every digit of the number
        for (int i = 0; i < n; i++)
        {
     
            // If no more digits can be replaced
            if (k < 1)
                break;
     
            // If current digit is not already 9
            if (str[i] != '9')
            {
     
                // Replace it with 9
                str[i] = '9';
     
                // One digit has been used
                k--;
            }
        }
        return str;
    }
     
    // Driver code
    public static void Main ()
    {
        StringBuilder str = new StringBuilder("569431");
         
        int n = str.Length;
        int k = 3;
     
        Console.WriteLine(findMaximumNum(str, n, k));
    }
}
 
// This code is contributed by ihritik

<script>
      // JavaScript implementation of the approach
      // Function to return the maximum number
      // that can be formed by changing
      // at most k digits in str
      function findMaximumNum(str, n, k) {
        // For every digit of the number
        for (var i = 0; i < n; i++) {
          // If no more digits can be replaced
          if (k < 1) break;
 
          // If current digit is not already 9
          if (str[i] !== "9") {
            // Replace it with 9
            str[i] = "9";
 
            // One digit has been used
            k--;
          }
        }
        return str.join("");
      }
 
      // Driver code
      var str = "569431";
      var n = str.length;
      var k = 3;
 
      document.write(findMaximumNum(str.split(""), n, k));
    </script>

999931

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)