Tiempo mínimo requerido para completar todas las tareas con alteración de su orden permitida

Dada una string S que consta de N caracteres (que representan las tareas a realizar) y un número entero positivo K , la tarea es encontrar el tiempo mínimo requerido para completar todas las tareas dadas en cualquier orden, dado que cada tarea toma una unidad de tiempo y cada tarea del mismo tipo debe realizarse en un intervalo de K unidades .

Ejemplos:

Entrada: S = “AAABBB”, K = 2
Salida: 8
Explicación:
A continuación se muestra el orden de la tarea que se debe completar:
A → B → _ → A → B → _ → A → B 
Por lo tanto, el tiempo total requerido es 8 unidades

Entrada: S = “AAABBB”, K = 0
Salida: 6

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Para completar las tareas en un tiempo mínimo, la idea es encontrar el máximo de caracteres que ocurren en la array y completar esas tareas primero.
• Sea X el carácter máximo que aparece y su frecuencia sea freq .
• Ahora, para completar primero las tareas de tipo X , debe haber una diferencia de K entre ellas, lo que deja un número total de (frecuencia – 1) * K ranuras vacías entre las tareas de X.
• Luego, llene estos espacios vacíos recorriendo las otras tareas ya que las otras tareas tienen una frecuencia menor o igual a la de X .

Siga los pasos a continuación para resolver el problema:

• Inicialice un HashMap , digamos M , que almacene la frecuencia de cada carácter en la string dada S.
• Inicialice dos variables, maxchar y maxfreq , que almacenan el carácter máximo que ocurre y su frecuencia, respectivamente.
• Recorra la string dada S e incremente la frecuencia de S[i] en el mapa M y si es mayor que maxfreq ,   actualice el valor de maxchar a S[i] y el valor de maxfreq a su frecuencia.
• Almacene el número de ranuras vacías en una variable, digamos S , como (maxfreq – 1) * K.
• Atraviese el HashMap , M y para cada carácter que no sea maxchar , actualice el valor de los espacios vacíos, S restando el mínimo de (maxfreq – 1) y M[S[i]] de S .
• Almacene el tiempo mínimo requerido en una variable, y como suma de N y S , si el valor de S ≥ 0 .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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 minimum time
// required to complete the tasks if
// the order of tasks can be changed
void findMinimumTime(string& S, int N,
                     int K)
{
    // If there is no task, print 0
    if (N == 0) {
        cout << 0;
        return;
    }
 
    // Store the maximum occurring
    // character and its frequency
    int maxfreq = INT_MIN;
    char maxchar;
 
    // Stores the frequency of each
    // character
    unordered_map<char, int> um;
 
    // Traverse the string S
    for (int i = 0; i < N; i++) {
 
        // Increment the frequency of
        // the current character
        um[S[i]]++;
 
        // Update maxfreq and maxchar
        if (um[S[i]] > maxfreq) {
            maxfreq = um[S[i]];
            maxchar = S[i];
        }
    }
 
    // Store the number of empty slots
    int emptySlots = (maxfreq - 1) * K;
 
    // Traverse the hashmap, um
    for (auto& it : um) {
 
        if (it.first == maxchar)
            continue;
 
        // Fill the empty slots
        emptySlots -= min(it.second,
                          maxfreq - 1);
    }
 
    // Store the required result
    int ans = N + max(0, emptySlots);
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    string S = "AAABBB";
    int K = 2;
    int N = S.length();
    findMinimumTime(S, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.HashMap;
import java.util.Map;
 
class GFG{
 
// Function to find the minimum time
// required to complete the tasks if
// the order of tasks can be changed
static void findMinimumTime(String S, int N, int K)
{
     
    // If there is no task, print 0
    if (N == 0)
    {
        System.out.println(0);
        return;
    }
 
    // Store the maximum occurring
    // character and its frequency
    int maxfreq = Integer.MIN_VALUE;
    char maxchar = ' ';
 
    // Stores the frequency of each
    // character
    HashMap<Character, Integer> um = new HashMap<>();
 
    // Traverse the string S
    for(int i = 0; i < N; i++)
    {
         
        // Increment the frequency of
        // the current character
        um.put(S.charAt(i),
               um.getOrDefault(S.charAt(i), 0) + 1);
 
        // Update maxfreq and maxchar
        if (um.get(S.charAt(i)) > maxfreq)
        {
            maxfreq = um.get(S.charAt(i));
            maxchar = S.charAt(i);
        }
    }
 
    // Store the number of empty slots
    int emptySlots = (maxfreq - 1) * K;
 
    // Traverse the hashmap, um
    for(Map.Entry<Character, Integer> it :
        um.entrySet())
    {
        if (it.getKey() == maxchar)
            continue;
 
        // Fill the empty slots
        emptySlots -= Math.min(
            it.getValue(), maxfreq - 1);
    }
 
    // Store the required result
    int ans = N + Math.max(0, emptySlots);
 
    // Print the result
    System.out.println(ans);
}
 
// Driver code
public static void main(String[] args)
{
    String S = "AAABBB";
    int K = 2;
    int N = S.length();
     
    findMinimumTime(S, N, K);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
import sys
from collections import defaultdict
 
# Function to find the minimum time
# required to complete the tasks if
# the order of tasks can be changed
def findMinimumTime(S, N, K):
     
    # If there is no task, print 0
    if (N == 0):
        print(0)
        return
 
    # Store the maximum occurring
    # character and its frequency
    maxfreq = -sys.maxsize
 
    # Stores the frequency of each
    # character
    um = defaultdict(int)
 
    # Traverse the string S
    for i in range(N):
 
        # Increment the frequency of
        # the current character
        um[S[i]] += 1
 
        # Update maxfreq and maxchar
        if (um[S[i]] > maxfreq):
            maxfreq = um[S[i]]
            maxchar = S[i]
 
    # Store the number of empty slots
    emptySlots = (maxfreq - 1) * K
 
    # Traverse the hashmap, um
    for it in um:
        if (it == maxchar):
            continue
 
        # Fill the empty slots
        emptySlots -= min(um[it],
                          maxfreq - 1)
 
    # Store the required result
    ans = N + max(0, emptySlots)
 
    # Print the result
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    S = "AAABBB"
    K = 2
    N = len(S)
     
    findMinimumTime(S, N, K)
     
# This code is contributed by ukasp

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the minimum time
// required to complete the tasks if
// the order of tasks can be changed
static void findMinimumTime(string S, int N, int K)
{
     
    // If there is no task, print 0
    if (N == 0)
    {
        Console.Write(0);
        return;
    }
 
    // Store the maximum occurring
    // character and its frequency
    int maxfreq = Int32.MinValue;
    char maxchar = ' ';
 
    // Stores the frequency of each
    // character
    Dictionary<char,
               int> um = new Dictionary<char,
                                        int>();
 
    // Traverse the string S
    for(int i = 0; i < N; i++)
    {
         
        // Increment the frequency of
        // the current character
        if (um.ContainsKey(S[i]))
            um[S[i]]++;
        else
            um.Add(S[i], 1);
 
        // Update maxfreq and maxchar
        if (um.ContainsKey(S[i]) &&
            um[S[i]] > maxfreq)
        {
            maxfreq = um[S[i]];
            maxchar = S[i];
        }
    }
 
    // Store the number of empty slots
    int emptySlots = (maxfreq - 1) * K;
 
    // Traverse the hashmap, um
    foreach(KeyValuePair<char, int> kvp in um)
    {
 
        if (kvp.Key == maxchar)
            continue;
 
        // Fill the empty slots
        emptySlots -= Math.Min(kvp.Value,
                               maxfreq - 1);
    }
 
    // Store the required result
    int ans = N + Math.Max(0, emptySlots);
 
    // Print the result
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
    string S = "AAABBB";
    int K = 2;
    int N = S.Length;
     
    findMinimumTime(S, N, K);
}
}
 
// This code is contributed by bgangwar59

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum time
// required to complete the tasks if
// the order of tasks can be changed
function findMinimumTime(s, N, K)
{
     
    // If there is no task, print 0
    if (N == 0)
    {
        document.write(0);
        return;
    }
 
    // Store the maximum occurring
    // character and its frequency
    let maxfreq = Number.MIN_SAFE_INTEGER;
    let maxchar;
 
    // Stores the frequency of each
    // character
    let um = new Map();
 
    // Traverse the string S
    for(let i = 0; i < N; i++)
    {
         
        // Increment the frequency of
        // the current character
        if (um.has(s[i]))
        {
           um.set(s[i], um.get(s[i]) + 1)
        }
        else
        {
            um.set(s[i], 1)
        }
 
        // Update maxfreq and maxchar
        if (um.get(S[i]) > maxfreq)
        {
            maxfreq = um.get(S[i]);
            maxchar = S[i];
        }
    }
 
    // Store the number of empty slots
    let emptySlots = (maxfreq - 1) * K;
 
    // Traverse the hashmap, um
    for(let it of um)
    {
        if (it[0] == maxchar)
            continue;
 
        // Fill the empty slots
        emptySlots -= Math.min(
            it[1], maxfreq - 1);
    }
 
    // Store the required result
    let ans = N + Math.max(0, emptySlots);
 
    // Print the result
    document.write(ans);
}
 
// Driver Code
let S = "AAABBB";
let K = 2;
let N = S.length;
 
findMinimumTime(S, N, K);
 
// This code is contributed by _saurabh_jaiswal.
 
</script>

8

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