String lexicográficamente más pequeña formada al agregar un carácter de los primeros K caracteres de una string dada

Dada una string S que consta de alfabetos en minúsculas. La tarea es encontrar la string X lexicográficamente más pequeña de la misma longitud que se pueda formar utilizando la operación que se indica a continuación:
En una sola operación, seleccione cualquier carácter entre los primeros K caracteres de la string S como máximo, elimínelo de la string S y añádalo a la string X. Aplique esta operación tantas veces como quiera.
Ejemplos: 
 

Entrada: str = “gaurang”, k=3 
Salida: agangru 
Quite ‘a’ en el primer paso y agregue a X. 
Quite ‘g’ en el segundo paso y agregue a X. 
Quite ‘a’ en el tercer paso y agregue a X. 
Elimine ‘n’ en el tercer paso y agregue a X. 
Elija el carácter lexicográficamente más pequeño en cada paso de los primeros K caracteres para obtener la 
string «agangru»
Entrada: str = «geeksforgeeks», k=5 
Salida: eefggeekkorss

Acercarse: 
 

• Encuentre el carácter más pequeño en los primeros k caracteres de la string S.
• Elimine el carácter más pequeño encontrado de la string.
• Agregue el carácter más pequeño encontrado a la nueva string X.
• Repita los pasos anteriores hasta que la string s esté vacía.

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

// C++ program to find the new string
// after performing deletions and append
// operation in the string s
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the new string thus
// formed by removing characters
string newString(string s, int k)
{
    // new string
    string X = "";
 
    // Remove characters until
    // the string  is empty
    while (s.length() > 0) {
 
        char temp = s[0];
 
        // Traverse to find the smallest character in the
        // first k characters
        for (long long i = 1; i < k and i < s.length(); i++) {
            if (s[i] < temp) {
                temp = s[i];
            }
        }
 
        // append the smallest character
        X = X + temp;
 
        // removing the lexicographically smallest
        // character from the string
        for (long long i = 0; i < k; i++) {
            if (s[i] == temp) {
 
                s.erase(s.begin() + i);
                break;
            }
        }
    }
 
    return X;
}
 
// Driver Code
int main()
{
 
    string s = "gaurang";
    int k = 3;
 
    cout << newString(s, k);
}

// Java program to find the new string
// after performing deletions and append
// operation in the string s
 
class GFG {
 
// Function to find the new string thus
// formed by removing characters
    static String newString(String s, int k) {
        // new string
        String X = "";
 
        // Remove characters until
        // the string  is empty
        while (s.length() > 0) {
 
            char temp = s.charAt(0);
 
            // Traverse to find the smallest character in the
            // first k characters
            for (int i = 1; i < k && i < s.length(); i++) {
                if (s.charAt(i) < temp) {
                    temp = s.charAt(i);
                }
            }
 
            // append the smallest character
            X = X + temp;
 
            // removing the lexicographically smallest
            // character from the string
            for (int i = 0; i < k; i++) {
                if (s.charAt(i) == temp) {
 
                    s = s.substring(0, i) + s.substring(i + 1);
                    //s.erase(s.begin() + i);
                    break;
                }
            }
        }
 
        return X;
    }
// Driver code
 
    public static void main(String[] args) {
        String s = "gaurang";
        int k = 3;
 
        System.out.println(newString(s, k));
 
    }
}
 
// This code contributed by Jajput-Ji

# Python 3 program to find the new string
# after performing deletions and append
# operation in the string s
 
# Function to find the new string thus
# formed by removing characters
def newString(s, k):
     
    # new string
    X = ""
 
    # Remove characters until
    # the string is empty
    while (len(s) > 0):
        temp = s[0]
 
        # Traverse to find the smallest
        # character in the first k characters
        i = 1
        while(i < k and i < len(s)):
            if (s[i] < temp):
                temp = s[i]
 
            i += 1
         
        # append the smallest character
        X = X + temp
 
        # removing the lexicographically
        # smallest character from the string
        for i in range(k):
            if (s[i] == temp):
                s = s[0:i] + s[i + 1:]
                break
         
    return X
 
# Driver Code
if __name__ == '__main__':
    s = "gaurang"
    k = 3
    print(newString(s, k))
 
# This code is contributed by
# Shashank_Sharma

// C# program to find the new string
// after performing deletions and
// append operation in the string s
using System;
 
class GFG
{
 
// Function to find the new string thus
// formed by removing characters
static String newString(String s, int k)
{
    // new string
    String X = "";
 
    // Remove characters until
    // the string is empty
    while (s.Length > 0)
    {
        char temp = s[0];
 
        // Traverse to find the smallest
        // character in the first k characters
        for (int i = 1; i < k && i < s.Length; i++)
        {
            if (s[i] < temp)
            {
                temp = s[i];
            }
        }
 
        // append the smallest character
        X = X + temp;
 
        // removing the lexicographically smallest
        // character from the string
        for (int i = 0; i < k; i++)
        {
            if (s[i] == temp)
            {
 
                s = s.Substring(0, i) + s.Substring(i + 1);
                //s.erase(s.begin() + i);
                break;
            }
        }
    }
 
    return X;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "gaurang";
    int k = 3;
 
    Console.Write(newString(s, k));
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to find the new string
// after performing deletions and
// append operation in the string s
 
// Function to find the new string thus
// formed by removing characters
function newString($s, $k)
{
    // new string
    $X = "";
 
    // Remove characters until
    // the string is empty
    while (strlen($s) > 0)
    {
        $temp = $s[0];
 
        // Traverse to find the smallest
        // character in the first k characters
        for ($i = 1; $i < $k &&
             $i < strlen($s); $i++)
        {
            if ($s[$i] < $temp)
            {
                $temp = $s[$i];
            }
        }
 
        // append the smallest character
        $X = $X . $temp;
 
        // removing the lexicographically smallest
        // character from the string
        for ($i = 0; $i < $k; $i++)
        {
            if ($s[$i] == $temp)
            {
 
                $s = substr($s, 0, $i) .
                     substr($s, $i + 1, strlen($s));
                      
                //s.erase(s.begin() + i);
                break;
            }
        }
    }
 
    return $X;
}
 
// Driver code
$s = "gaurang";
$k = 3;
 
echo(newString($s, $k));
 
// This code contributed by mits
?>

<script>
 
      // JavaScript program to find the new string
      // after performing deletions and
      // append operation in the string s
       
      // Function to find the new string thus
      // formed by removing characters
      function newString(s, k) {
        // new string
        var X = "";
 
        // Remove characters until
        // the string is empty
        while (s.length > 0) {
          var temp = s[0];
 
          // Traverse to find the smallest
          // character in the first k characters
          for (var i = 1; i < k && i < s.length; i++)
          {
            if (s[i] < temp) {
              temp = s[i];
            }
          }
 
          // append the smallest character
          X = X + temp;
 
          // removing the lexicographically smallest
          // character from the string
          for (var i = 0; i < k; i++) {
            if (s[i] === temp) {
              s = s.substring(0, i) + s.substring(i + 1);
 
              break;
            }
          }
        }
 
        return X;
      }
 
      // Driver code
      var s = "gaurang";
      var k = 3;
 
      document.write(newString(s, k));
       
</script>

agangru

Complejidad de tiempo: O(n*n), ya que se utilizan bucles anidados
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional