La string más grande obtenida en el orden del Diccionario después de eliminar K caracteres

Dada la string str de longitud N y un entero K , la tarea es devolver la string más grande en Orden de diccionario borrando K caracteres de esa string.

El orden de diccionario de string más grande es la última string cuando las strings se organizan en orden alfabético.

Ejemplos:

Entrada: str = “ritz” K = 2
Salida: tz
Explicación:
Hay 6 formas posibles de borrar dos caracteres de s: “ri”, “rt”, “rz”, “it”, “iz”, “tz” . 
Entre estas strings, «tz» es la más grande en el orden del diccionario. 
Por lo tanto, «tz» es la salida deseada.

Entrada: str = “jackie” K = 2
Salida: jkie
Explicación:
Los caracteres “a” y “c” se eliminan para obtener la string más grande posible.

Enfoque ingenuo: la idea es encontrar toda la subsecuencia de la longitud de string dada N – K. Almacena esas subsecuencias en una lista. Habrá ⁿ C _m Tales secuencias. Después de los pasos anteriores, imprima la string más grande en orden alfabético almacenada en la lista.

Complejidad de tiempo:  O (2 ^N-K )

Enfoque Eficiente: La idea es utilizar un Deque . A continuación se muestran los pasos:

1. Almacene todos los caracteres de la string en el deque.
2. Recorra la string dada y, para cada carácter de la string, siga extrayendo los caracteres de deque si es menor que el último carácter almacenado en deque. Realice esta operación hasta que K sea distinto de cero.
3. Ahora, después de las operaciones anteriores, inserte el carácter actual en el deque.
4. Después de las operaciones anteriores, la string formada por los caracteres almacenados en el deque es la string resultante.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest
// string after deleting k characters
string largestString(int n, int k, string s)
{
     
    // Deque dq used to find the
    // largest string in dictionary
    // after deleting k characters
    deque<char> deq;
 
    // Iterate till the length
    // of the string
    for(int i = 0; i < n; ++i)
    {
         
        // Condition for popping
        // characters from deque
        while (deq.size() > 0 &&
               deq.back() < s[i] &&
                        k > 0)
        {
            deq.pop_front();
            k--;
        }
 
        deq.push_back(s[i]);
    }
 
    // To store the resultant string
    string st = "";
 
    // To form resultant string
    for(char c : deq)
        st = st + c;
 
    // Return the resultant string
    return st;
}
 
// Driver code   
int main()
{
    int n = 4;
    int k = 2;
 
    // Given String
    string sc = "ritz";
 
    // Function call
    string result = largestString(n, k, sc);
 
    // Print the answer
    cout << result << endl;
         
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

// Java program for the above approach
 
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.io.IOException;
 
public class GFG {
 
    // Function to find the largest
    // string after deleting k characters
    public static String
    largestString(int n, int k, String sc)
    {
        char[] s = sc.toCharArray();
 
        // Deque dq used to find the
        // largest string in dictionary
        // after deleting k characters
        Deque<Character> deq
            = new ArrayDeque<>();
 
        // Iterate till the length
        // of the string
        for (int i = 0; i < n; ++i) {
 
            // Condition for popping
            // characters from deque
            while (deq.size() > 0
                   && deq.getLast() < s[i]
                   && k > 0) {
                deq.pollLast();
                k--;
            }
 
            deq.add(s[i]);
        }
 
        // To store the resultant string
        String st = "";
 
        // To form resultant string
        for (char c : deq)
            st = st + Character.toString(c);
 
        // Return the resultant string
        return st;
    }
 
    // Driver Code
    public static void main(String[] args)
        throws IOException
    {
        int n = 4;
        int k = 2;
 
        // Given String
        String sc = "ritz";
 
        // Function call
        String result = largestString(n, k, sc);
 
        // Print the answer
        System.out.println(result);
    }
}

# Python3 program for the above approach
from collections import deque
 
# Function to find the largest
# string after deleting k characters
def largestString(n, k, sc):
     
    s = [i for i in sc]
 
    # Deque dq used to find the
    # largest string in dictionary
    # after deleting k characters
    deq = deque()
 
    # Iterate till the length
    # of the string
    for i in range(n):
 
        # Condition for popping
        # characters from deque
        while (len(deq) > 0 and
                deq[-1] < s[i] and
                      k > 0):
            deq.popleft()
            k -= 1
 
        deq.append(s[i])
 
    # To store the resultant string
    st = ""
 
    # To form resultant string
    for c in deq:
        st = st + c
 
    # Return the resultant string
    return st
 
# Driver Code
if __name__ == '__main__':
     
    n = 4
    k = 2
 
    # Given String
    sc = "ritz"
 
    # Function call
    result = largestString(n, k, sc)
 
    # Print the answer
    print(result)
 
# This code is contributed by mohit kumar 29

<script>
 
// Javascript program for the above approach
 
// Function to find the largest
// string after deleting k characters
function largestString(n, k, s)
{
     
    // Deque dq used to find the
    // largest string in dictionary
    // after deleting k characters
    var deq = [];
 
    // Iterate till the length
    // of the string
    for(var i = 0; i < n; ++i)
    {
         
        // Condition for popping
        // characters from deque
        while (deq.length > 0 &&
               deq[deq.length - 1] < s[i] &&
                            k > 0)
        {
            deq.shift();
            k--;
        }
        deq.push(s[i]);
    }
 
    // To store the resultant string
    var st = "";
 
    // To form resultant string
    deq.forEach(c => {
        st = st + c;
    });
 
    // Return the resultant string
    return st;
}
 
// Driver code   
var n = 4;
var k = 2;
 
// Given String
var sc = "ritz";
 
// Function call
var result = largestString(n, k, sc);
 
// Print the answer
document.write(result);
 
// This code is contributed by rutvik_56
 
</script>

tz

Complejidad temporal: O(N)
Espacio auxiliar: O(N)