Encuentre la longitud de la subsecuencia más larga con los primeros K alfabetos que tienen la misma frecuencia

Dada la string str con caracteres en mayúsculas y un número entero K , la tarea es encontrar la longitud de la subsecuencia más larga tal que la frecuencia del primer alfabeto K sea la misma.

Ejemplos: 

Entrada: str = “ACAABCCAB”, K=3 
Salida: 6 
Explicación: Una de las posibles subsecuencias es “ACABCB”.

Entrada: str = “ACAABCCAB”, K=4 
Salida: 0 
Explicación: Dado que la string no contiene ‘D’, no se puede obtener tal subsecuencia.  

Enfoque: 
Atraviese la string y encuentre el menos frecuente de los primeros K alfabetos. Una vez encontrado, (frecuencia de ese elemento) * K da el resultado deseado.
A continuación se muestra la implementación del enfoque anterior:

// C++ program to find the longest
// subsequence with first K
// alphabets having same frequency
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// length of the longest
// subsequence with first K
// alphabets having same frequency
int lengthOfSubsequence(string str,
                            int K)
{
    // Map to store frequency
    // of all characters in
    // the string
    map<char,int> mp;
    for (char ch : str) {
        mp[ch]++;
    }
     
    // Variable to store the
    // frequency of the least
    // frequent of first K
    // alphabets
    int minimum = mp['A'];
    for (int i = 1; i < K; i++) {
        minimum = min(minimum,
                    mp[(char)(i + 'A')]);
    }
     
    return minimum * K;
}
 
int main()
{
    string str = "ACAABCCAB";
    int K = 3;
     
    cout << lengthOfSubsequence(str, K);
    return 0;
}

// Java program to find the longest
// subsequence with first K alphabets
// having same frequency
import java.util.*;
 
class GFG{
 
// Function to return the
// length of the longest
// subsequence with first K
// alphabets having same frequency
static int lengthOfSubsequence(String str,
                            int K)
{
     
    // Map to store frequency
    // of all characters in
    // the string
    Map<Character, Integer> mp = new HashMap<>();
    for(char ch : str.toCharArray())
    {
        mp.put(ch, mp.getOrDefault(ch, 0) + 1);
    }
 
    // Variable to store the
    // frequency of the least
    // frequent of first K
    // alphabets
    int minimum = mp.get('A');
    for(int i = 1; i < K; i++)
    {
        minimum = Math.min(minimum,
                        mp.get((char)(i + 'A')));
    }
    return minimum * K;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "ACAABCCAB";
    int K = 3;
     
    System.out.println(lengthOfSubsequence(str, K));
}
}
 
// This code is contributed by offbeat

# Python3 program to find the longest
# subsequence with first K alphabets
# having same frequency
from collections import defaultdict
 
# Function to return the
# length of the longest
# subsequence with first K
# alphabets having same frequency
def lengthOfSubsequence(st, K):
 
    # Map to store frequency
    # of all characters in
    # the string
    mp = defaultdict(int)
    for ch in st:
        mp[ch] += 1
     
    # Variable to store the
    # frequency of the least
    # frequent of first K
    # alphabets
    minimum = mp['A']
     
    for i in range(1, K):
        minimum = min(minimum,
                    mp[chr(i + ord('A'))])
     
    return (minimum * K)
 
# Driver code
if __name__ == "__main__":
     
    st = "ACAABCCAB"
    K = 3
     
    print(lengthOfSubsequence(st, K))
 
# This code is contributed by chitranayal

// C# program to find the longest
// subsequence with first K alphabets
// having same frequency
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the
// length of the longest
// subsequence with first K
// alphabets having same frequency
static int lengthOfSubsequence(string str,
                               int K)
{
     
    // Store frequency
    // of all characters in
    // the string
    Dictionary<char,
               int> mp = new Dictionary<char,
                                        int>();
     
    foreach(char ch in str.ToCharArray())
    {
        mp[ch] = mp.GetValueOrDefault(ch, 0) + 1;
    }
 
    // Variable to store the frequency
    // of the least frequent of first K
    // alphabets
    int minimum = mp['A'];
    for(int i = 1; i < K; i++)
    {
        minimum = Math.Min(minimum,
                           mp[(char)(i + 'A')]);
    }
    return minimum * K;
}
 
// Driver code
public static void Main(string[] args)
{
    string str = "ACAABCCAB";
    int K = 3;
     
    Console.Write(lengthOfSubsequence(str, K));
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program to find the longest
// subsequence with first K
// alphabets having same frequency
 
// Function to return the
// length of the longest
// subsequence with first K
// alphabets having same frequency
function lengthOfSubsequence(str, K)
{
    // Map to store frequency
    // of all characters in
    // the string
    var mp = new Map();
 
    str.split('').forEach(ch => {
        if(mp.has(ch))
            mp.set(ch, mp.get(ch)+1)
        else   
            mp.set(ch, 1)
    });
     
    // Variable to store the
    // frequency of the least
    // frequent of first K
    // alphabets
    var minimum = mp.get('A');
    for (var i = 1; i < K; i++) {
        minimum = Math.min(minimum,
                    mp.get(String.fromCharCode(i + 'A'.charCodeAt(0))));
    }
     
    return minimum * K;
}
 
var str = "ACAABCCAB";
var K = 3;
 
document.write( lengthOfSubsequence(str, K));
 
 
 
</script>

6