Sufijo más largo tal que la aparición de cada carácter es menor que N después de eliminar como máximo K caracteres

Dada una string S y dos enteros N y K , la tarea es encontrar el sufijo de longitud máxima de modo que la aparición de cada carácter en la string de sufijo sea menor que N y se puedan eliminar como máximo K elementos de la string de entrada para obtener el sufijo de longitud máxima .
Ejemplos: 
 

Entrada: S = “iahagafedcba”, N = 1, K = 0 
Salida: fedcba 
Explicación: 
Sufijo de longitud máxima en la string dada 
Tal que la ocurrencia de cada carácter es 1 es “fedcba”, 
Porque si tomamos la string “afedcba”, 
entonces la aparición del carácter «a» será 2.
Entrada: S = «iahagafedcba», N = 1, K = 2 
Salida: hgfedcba 
Explicación: 
Sufijo de longitud máxima en la string dada 
Tal que la aparición de cada carácter es 1 es «hgfedcba ”, 
Después de borrar el carácter “a” dos veces. 
 

Enfoque: la idea es usar hash-map para almacenar la frecuencia de los caracteres de la string. 
 

• Inicialice una string vacía para almacenar el sufijo más largo de la string.
• Iterar la string desde la última usando un bucle – 
  • Incrementa la aparición del carácter en 1 en el mapa hash
  • Si la aparición del carácter actual es menor que N, agregue el carácter a la string de sufijo
  • De lo contrario, disminuya el valor de K en 1 si el valor de K es mayor que 0
• Imprime la string de sufijo.

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

// C++ implementation to find
// longest suffix of the string
// such that occurrence of each
// character is less than K
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// length suffix in the string
void maximumSuffix(string s,
               int n, int k){
     
    // Length of the string
    int i = s.length() - 1;
 
    // Map to store the number
    // of occurrence of character
    int arr[26] = { 0 };
    string suffix = "";
 
    // Loop to iterate string
    // from the last character
    while (i > -1) {
 
        int index = s[i] - 'a';
         
        // Condition to check if the
        // occurrence of each character
        // is less than given number
        if (arr[index] < n) {
            arr[index]++;
            suffix += s[i];
            i--;
            continue;
        }
         
        // Condition when character
        // cannot be deleted
        if (k == 0)
            break;
        k--;
        i--;
    }
    reverse(suffix.begin(), suffix.end());
 
    // Longest suffix
    cout << suffix;
}
 
// Driver Code
int main()
{
    string str = "iahagafedcba";
 
    int n = 1, k = 2;
     
    // Function call
    maximumSuffix(str, n, k);
    return 0;
}

// Java implementation to find
// longest suffix of the String
// such that occurrence of each
// character is less than K
class GFG{
 
// Function to find the maximum
// length suffix in the String
static void maximumSuffix(String s,
            int n, int k){
     
    // Length of the String
    int i = s.length() - 1;
 
    // Map to store the number
    // of occurrence of character
    int arr[] = new int[26];
    String suffix = "";
     
    // Loop to iterate String
    // from the last character
    while (i > -1) {
 
        int index = s.charAt(i) - 'a';
         
        // Condition to check if the
        // occurrence of each character
        // is less than given number
        if (arr[index] < n) {
            arr[index]++;
            suffix += s.charAt(i);
            i--;
            continue;
        }
         
        // Condition when character
        // cannot be deleted
        if (k == 0)
            break;
        k--;
        i--;
    }
    suffix = reverse(suffix);
     
    // Longest suffix
    System.out.print(suffix);
}
static String reverse(String input) {
    char[] a = input.toCharArray();
    int l, r = a.length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.valueOf(a);
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "iahagafedcba";
 
    int n = 1, k = 2;
     
    // Function call
    maximumSuffix(str, n, k);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 implementation to find
# longest suffix of the string
# such that occurrence of each
# character is less than K
 
# Function to find the maximum
# length suffix in the string
def maximumSuffix(s, n, k):
     
    # Length of the string
    i = len(s)- 1
 
    # Map to store the number
    # of occurrence of character
    arr = [0 for i in range(26)]
    suffix = ""
     
    # Loop to iterate string
    # from the last character
    while (i > -1):
        index = ord(s[i]) - ord('a');
         
        # Condition to check if the
        # occurrence of each character
        # is less than given number
        if (arr[index] < n):
            arr[index] += 1
            suffix += s[i]
            i -= 1
            continue
         
        # Condition when character
        # cannot be deleted
        if (k == 0):
            break
        k -= 1
        i -= 1
     
    suffix = suffix[::-1]
     
    # Longest suffix
    print(suffix)
 
# Driver Code
if __name__ == '__main__':
    str = "iahagafedcba"
 
    n = 1
    k = 2
     
    # Function call
    maximumSuffix(str, n, k)
 
# This code is contributed by Surendra_Gangwar

// C# implementation to find
// longest suffix of the String
// such that occurrence of each
// character is less than K
using System;
 
class GFG{
  
// Function to find the maximum
// length suffix in the String
static void maximumSuffix(String s,
            int n, int k){
      
    // Length of the String
    int i = s.Length - 1;
  
    // Map to store the number
    // of occurrence of character
    int []arr = new int[26];
    String suffix = "";
      
    // Loop to iterate String
    // from the last character
    while (i > -1) {
  
        int index = s[i] - 'a';
          
        // Condition to check if the
        // occurrence of each character
        // is less than given number
        if (arr[index] < n) {
            arr[index]++;
            suffix += s[i];
            i--;
            continue;
        }
          
        // Condition when character
        // cannot be deleted
        if (k == 0)
            break;
        k--;
        i--;
    }
    suffix = reverse(suffix);
      
    // longest suffix
    Console.Write(suffix);
}
static String reverse(String input) {
    char[] a = input.ToCharArray();
    int l, r = a.Length - 1;
    for (l = 0; l < r; l++, r--) {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.Join("",a);
}
  
// Driver Code
public static void Main(String[] args)
{
    String str = "iahagafedcba";
  
    int n = 1, k = 2;
      
    // Function call
    maximumSuffix(str, n, k);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation to find
// longest suffix of the string
// such that occurrence of each
// character is less than K
 
// Function to find the maximum
// length suffix in the string
function maximumSuffix(s,n, k){
     
    // Length of the string
    let i = s.length - 1;
 
    // Map to store the number
    // of occurrence of character
    let arr = new Array(26).fill(0);
    let suffix = "";
 
    // Loop to iterate string
    // from the last character
    while (i > -1) {
 
        let index = s.charCodeAt(i) - 97;
         
        // Condition to check if the
        // occurrence of each character
        // is less than given number
        if (arr[index] < n) {
            arr[index]++;
            suffix += s[i];
            i--;
            continue;
        }
         
        // Condition when character
        // cannot be deleted
        if (k == 0)
            break;
        k--;
        i--;
    }
    suffix = suffix.split("").reverse().join("");
 
    // Longest suffix
    document.write(suffix);
}
 
// Driver Code
let str = "iahagafedcba";
 
let n = 1, k = 2;
 
// Function call
maximumSuffix(str, n, k);
 
// This code is contributed by shinjanpatra.
</script>

hgfedcba

Análisis de rendimiento: 
 

• Complejidad de tiempo: en el enfoque anterior, hay un ciclo para iterar sobre una string que toma el tiempo O (L) en el peor de los casos. Por lo tanto, la complejidad temporal para este enfoque será O(L) .
• Complejidad del espacio auxiliar: en el enfoque anterior, se utiliza espacio adicional para almacenar la frecuencia del carácter. Por lo tanto, la complejidad del espacio auxiliar para el enfoque anterior será O(L)