Subsecuencia lexicográficamente más grande tal que cada carácter aparece al menos k veces

Dada una string S y un entero K . La tarea es encontrar la subsecuencia lexicográficamente más grande de S, digamos T, tal que cada carácter en T debe ocurrir al menos K veces.

Ejemplos: 

Input : S = "banana", K = 2.
Output : nn
Possible subsequence where each character exists at least 2 times are:

From the above subsequences, "nn" is the lexicographically largest.

La idea es resolver con avidez el problema anterior. Si queremos que la subsecuencia sea lexicográficamente más grande, debemos dar prioridad a los caracteres lexicográficamente más grandes. ‘z’ es el carácter más grande, supongamos que z aparece f _z veces en S. Si f _z >= K, agregue ‘z’z k veces en la string T y siga eliminando caracteres de la izquierda de S hasta que todas las z estén remoto. Aplicar la estrategia con ‘y’, ‘w’, ….., ‘a’. Al final, encontrarás la respuesta.

Veamos un ejemplo. Suponga que S = “zzwzawa” y K = 2. Comience con el carácter más grande ‘z’. Aquí f _z = 3 >= K. Así que T se convertirá en “zzz” y quitaremos las letras de la izquierda de S hasta que se eliminen todas las z. Así que ahora S se convertirá en «awa». El siguiente más grande es ‘y’, pero eso ocurre 0 veces en k, por lo que lo omitiremos. Omitiremos ‘w’, ‘v’, etc. también hasta que vayamos a ‘a’ que ocurre 2 veces. Ahora T se convertirá en «zzzaa» y S se convertirá en una string vacía. Nuestra respuesta es “zzzaa”.

A continuación se muestra la implementación de este enfoque: 

// C++ program to find lexicographically largest
// subsequence where every character appears at
// least k times.
#include <bits/stdc++.h>
using namespace std;
 
// Find lexicographically largest subsequence of
// s[0..n-1] such that every character appears
// at least k times. The result is filled in t[]
void subsequence(char s[], char t[], int n, int k)
{
    int last = 0, cnt = 0, new_last = 0, size = 0;
 
    // Starting from largest character 'z' to 'a'
    for (char ch = 'z'; ch >= 'a'; ch--) {
        cnt = 0;
 
        // Counting the frequency of the character
        for (int i = last; i < n; i++) {
            if (s[i] == ch)
                cnt++;
        }
 
        // If frequency is greater than k
        if (cnt >= k) {
 
            // From the last point we leave
            for (int i = last; i < n; i++) {
 
                // check if string contain ch
                if (s[i] == ch) {
 
                    // If yes, append to output string
                    t[size++] = ch;
                    new_last = i;
                }
            }
 
            // Update the last point.
            last = new_last;
        }
    }
    t[size] = '\0';
}
 
// Driver code
int main()
{
    char s[] = "banana";
    int n = sizeof(s);
    int k = 2;
    char t[n];
    subsequence(s, t, n - 1, k);
    cout << t << endl;
    return 0;
}

import java.util.Arrays;
 
 
// Java program to find lexicographically largest
// subsequence where every character appears at
// least k times. 
class GFG {
 
// Find lexicographically largest subsequence of
// s[0..n-1] such that every character appears
// at least k times. The result is filled in t[]
static void subsequence(char s[], char t[], int n, int k)
{
    int last = 0, cnt = 0, new_last = 0, size = 0;
  
    // Starting from largest character 'z' to 'a'
    for (char ch = 'z'; ch >= 'a'; ch--) {
        cnt = 0;
  
        // Counting the frequency of the character
        for (int i = last; i < n; i++) {
            if (s[i] == ch)
                cnt++;
        }
  
        // If frequency is greater than k
        if (cnt >= k) {
  
            // From the last point we leave
            for (int i = last; i < n; i++) {
  
                // check if string contain ch
                if (s[i] == ch) {
  
                    // If yes, append to output string
                    t[size++] = ch;
                    new_last = i;
                }
            }
  
            // Update the last point.
            last = new_last;
        }
    }
    t[size] = '\0';
}
  
// Driver code
    public static void main(String[] args) {
    char s[] = {'b','a','n','a','n','a'};
    int n = s.length;
    int k = 2;
    char t[] = new char[n];
    subsequence(s, t, n - 1, k);
    for(int i = 0;i<t.length;i++)
        if(t[i]!=0)
            System.out.print(t[i]);
     
    }
}
 
// This code is contributed by Jajput-Ji

# Python3 program to find lexicographically largest
# subsequence where every character appears at
# least k times.
 
# Find lexicographically largest subsequence of
# s[0..n-1] such that every character appears
# at least k times. The result is filled in t[]
def subsequence(s, t, n, k):
    last = 0
    cnt = 0
    new_last = 0
    size = 0
 
    string = 'zyxwvutsrqponmlkjihgfedcba'
 
    # Starting from largest character 'z' to 'a'
    for ch in string:
        cnt = 0
        for i in range(last, n):
            if s[i] == ch:
                cnt += 1
 
        # If frequency is greater than k
        if cnt >= k:
 
            # From the last point we leave
            for i in range(last, n):
 
                # check if string contain ch
                if s[i] == ch:
 
                    # If yes, append to output string
                    t[size] = ch
                    new_last = i
                    size += 1
 
            # Update the last point.
            last = new_last
 
# Driver Code
if __name__ == "__main__":
    s = ['b', 'a', 'n', 'a', 'n', 'a']
    n = len(s)
    k = 2
    t = [''] * n
    subsequence(s, t, n - 1, k)
    t = ''.join(t)
    print(t)
 
# This code is contributed by
# sanjeev2552

// C# program to find lexicographically
// largest subsequence where every
// character appears at least k times.
using System;
 
class GFG
{
 
// Find lexicographically largest subsequence
// of s[0..n-1] such that every character
// appears at least k times. The result is
// filled in t[]
static void subsequence(char []s, char []t,
                        int n, int k)
{
    int last = 0, cnt = 0,
        new_last = 0, size = 0;
 
    // Starting from largest character
    // 'z' to 'a'
    for (char ch = 'z'; ch >= 'a'; ch--)
    {
        cnt = 0;
 
        // Counting the frequency of
        // the character
        for (int i = last; i < n; i++)
        {
            if (s[i] == ch)
                cnt++;
        }
 
        // If frequency is greater than k
        if (cnt >= k)
        {
 
            // From the last point we leave
            for (int i = last; i < n; i++)
            {
 
                // check if string contain ch
                if (s[i] == ch)
                {
 
                    // If yes, append to output string
                    t[size++] = ch;
                    new_last = i;
                }
            }
 
            // Update the last point.
            last = new_last;
        }
    }
    t[size] = '\0';
}
 
// Driver code
public static void Main()
{
    char []s = {'b','a','n','a','n','a'};
    int n = s.Length;
    int k = 2;
    char []t = new char[n];
    subsequence(s, t, n - 1, k);
    for(int i = 0; i < t.Length; i++)
        if(t[i] != 0)
            Console.Write(t[i]);
}
}
 
// This code contributed by Rajput-Ji

<script>
 
 
// Javascript program to find
// lexicographically largest
// subsequence where every
// character appears at
// least k times.
 
// Find lexicographically largest subsequence of
// s[0..n-1] such that every character appears
// at least k times. The result is filled in t[]
function subsequence(s, t, n, k)
{
    var last = 0, cnt = 0, new_last = 0, size = 0;
 
    // Starting from largest character 'z' to 'a'
    for (var ch = 'z'.charCodeAt(0);
    ch >= 'a'.charCodeAt(0); ch--)
    {
        cnt = 0;
 
        // Counting the frequency of the character
        for (var i = last; i < n; i++) {
            if (s[i].charCodeAt(0) == ch)
                cnt++;
        }
 
        // If frequency is greater than k
        if (cnt >= k) {
 
            // From the last point we leave
            for (var i = last; i < n; i++) {
 
                // check if string contain ch
                if (s[i].charCodeAt(0) == ch) {
 
                    // If yes, append to output string
                    t[size++] = String.fromCharCode(ch);
                    new_last = i;
                }
            }
 
            // Update the last point.
            last = new_last;
        }
    }
}
 
// Driver code
var s = "banana";
var n = s.length;
var k = 2;
var t = Array(n);
subsequence(s, t, n - 1, k);
document.write( t.join('') );
 
 
</script>

nn

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

Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan (anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.