Construya una string con la frecuencia dada y la mínima ocurrencia continua de una letra

Construya una string que contenga una letra multiplicada por ‘A’ y b multiplicada por la letra ‘B’ (a > b) de modo que la aparición continua máxima de una letra sea lo más pequeña posible.

Ejemplos:

Entrada: a = 4, b = 3 
Salida: ABABABA
Explicación: Las otras formas posibles podrían ser “AAAABBB” o “AABBAAB”, etc. 
Pero “ABABABA” es la solución más óptima con mínima ocurrencia consecutiva.

Entrada: a = 5, b = 1
Salida: AABAAA

Enfoque: El enfoque del problema se basa en la siguiente observación:

Dado que a > b, se puede observar fácilmente que ‘B’ está dividiendo toda la string en (b+1) partes. 
De acuerdo con el principio del casillero , al menos una región debe tener al menos p = ⌈a/(b+1)⌉  A’s. Primero, coloque el número p de ‘A’ en cada región (b+1). Ahora las ‘A’ restantes pueden distribuirse equitativamente en las regiones.

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

• La región se divide en (b+1) partes. Así que ejecute un ciclo de 0 a (b+1) y comience a insertar para cada parte.
  • Primero, calcule cuál debería ser el valor actual de inserción de ‘A’ (Usando el principio de Pigeonhole p = ceil(a/(b+1)) ) para cada región izquierda.
  • Inserte p veces ‘A’ en la string y disminuya el valor de a .
  • Ahora se completa una región, así que inserte una ‘B’ y disminuya el valor de b .
  • Siga haciendo esto hasta que las restricciones de a y b le permitan hacerlo.
• Devuelve la string final como la respuesta.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct the string
string generateans(int a, int b)
{
    int temp = b + 1;
    string s;
 
    // Run a loop until b is greater than 0
    while (temp--) {
        int each = a / (b + 1);
        while (each--) {
            s.push_back('A');
            a--;
        }
        if (b > 0) {
            s.push_back('B');
            b--;
        }
    }
    return s;
}
 
// Driver code
int main()
{
    int a = 4, b = 3;
 
    // Function call
    cout << generateans(a, b);
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
    // Function to construct the string
    public static String generateans(int a, int b)
    {
        int temp = b + 1;
        String s = "";
 
        // Run a loop until b is greater than 0
        while (temp-- > 0) {
            int each = a / (b + 1);
            while (each-- > 0) {
                s += 'A';
                a--;
            }
            if (b > 0) {
                s += 'B';
                b--;
            }
        }
        return s;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int a = 4, b = 3;
 
        // Function call
        System.out.print(generateans(a, b));
    }
}
 
// This code is contributed by Rohit Pradhan

# Python code to implement the approach
 
# Function to construct the string
def generateans(a, b):
    temp = b + 1
    s = ""
 
    # Run a loop until b is greater than 0
    while temp>0:
        each = (a // (b + 1))
        while each>0:
            s += 'A'
            a -= 1
            each -= 1
             
        if (b > 0):
            s += 'B'
            b -= 1
        temp -= 1
 
    return s
 
# Driver code
a,b = 4,3
 
# Function call
print(generateans(a, b))
 
# This code is contributed by shinjanpatra

// C# code to implement the approach
using System;
using System.Linq;
 
 
public class GFG
{
    // Function to construct the string
    public static string generateans(int a, int b)
    {
        int temp = b + 1;
        string s = "";
 
        // Run a loop until b is greater than 0
        while (temp-- > 0) {
            int each = a / (b + 1);
            while (each-- > 0) {
                s += 'A';
                a--;
            }
            if (b > 0) {
                s += 'B';
                b--;
            }
        }
        return s;
    }
 
  // Driver Code
  public static void Main(string[] args)
  {
       int a = 4, b = 3;
 
        // Function call
        Console.WriteLine(generateans(a, b));
  }
}
 
// This code is contributed by code_hunt.

<script>
    // JavaScript code to implement the approach
 
 
    // Function to construct the string
    const generateans = (a, b) => {
        let temp = b + 1;
        let s = "";
 
        // Run a loop until b is greater than 0
        while (temp--) {
            let each = parseInt(a / (b + 1));
            while (each--) {
                s += 'A';
                a--;
            }
            if (b > 0) {
                s += 'B';
                b--;
            }
        }
        return s;
    }
 
    // Driver code
 
    let a = 4, b = 3;
 
    // Function call
    document.write(generateans(a, b));
 
// This code is contributed by rakeshsahni
 
</script>

ABABABA

Tiempo Complejidad: O(a+b)
Espacio Auxiliar: O(1)