Recuento de strings de 3 longitudes utilizando caracteres dados que contienen al menos 2 caracteres diferentes

Dados tres enteros a , b y c que denotan las frecuencias de tres caracteres diferentes ‘ A ‘, ‘ B ‘ y ‘ C ‘ respectivamente, y pueden usarse para formar strings de longitud 3. La tarea es contar el número total de posibles combinaciones de A, B y C de modo que forme una string que tenga al menos 2 caracteres diferentes .

Ejemplo:

Entrada: a = 2, b = 3, c = 3
Salida: 2
Explicación: Las strings posibles que satisfacen las condiciones dadas son: {“ABC”, “ABC”}

Entrada: a = 5, b = 4, c = 3
Salida: 4

Enfoque: El número total de strings de longitud 3, que se pueden formar con las frecuencias dadas es (a+b+c)/3, suponiendo que se seleccione cualquier carácter para cualquier string. Pero como solo se requieren strings con 2 caracteres diferentes, es esencial verificar si eso es posible o no. Para comprobar que:

1. Suponga que todas las strings (a+b+c)/3 se forman hasta dos lugares solo con any y all tiene un espacio restante para llenar.
2. Ahora, hasta este punto, las strings son válidas porque:
   • Si la string tiene dos caracteres diferentes, entonces es válida.
   • Si la string tiene dos caracteres iguales, puede hacerse válida insertando un carácter diferente.
3. Entonces, el número total de caracteres diferentes que necesitamos es, digamos count where count = (a+b+c)/3 , asumiendo que se requiere un carácter para cada string.
4. Entonces, si la suma de las dos frecuencias más pequeñas excede count , entonces se pueden formar (a+b+c)/3 números de strings. De lo contrario, sería la suma de las dos frecuencias más pequeñas.

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count possible number of strings
// such that each string consists of atleast
// 2 different characters of length 3
int countStrings(int a, int b, int c)
{
    // Array to store the 3 frequencies
    int arr[3];
 
    arr[0] = a;
    arr[1] = b;
    arr[2] = c;
 
    // Total number of strings that can be
    // formed irrespective of the given
    // condition i.e, neglecting the condition
    // that each string consists of atleast 2
    // different characters of length 3
    int count = (arr[0] + arr[1] + arr[2]) / 3;
 
    // Sort the array
    sort(arr, arr + 3);
 
    // If the sum of smallest and 2nd largest
    // element is less than the count, then
    // assign the sum to count
    if (arr[0] + arr[1] < count) {
        count = arr[0] + arr[1];
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int a = 5, b = 4, c = 3;
 
    cout << countStrings(a, b, c);
 
    return 0;
}

// Java implementation for the above approach
import java.util.*;
 
class GFG
{
    // Function to count possible number of strings
    // such that each string consists of atleast
    // 2 different characters of length 3
    public static int countStrings(int a, int b, int c)
    {
       
        // Array to store the 3 frequencies
        int[] arr = new int[3];
 
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
 
        // Total number of strings that can be
        // formed irrespective of the given
        // condition i.e, neglecting the condition
        // that each string consists of atleast 2
        // different characters of length 3
        int count = (arr[0] + arr[1] + arr[2]) / 3;
 
        // Sort the array
        Arrays.sort(arr);
 
        // If the sum of smallest and 2nd largest
        // element is less than the count, then
        // assign the sum to count
        if (arr[0] + arr[1] < count) {
            count = arr[0] + arr[1];
        }
 
        // Return the count
        return count;
    }
 
    // Driver Code
    public static void main(String[] args) {
         
        int a = 5, b = 4, c = 3;
 
        System.out.println(countStrings(a, b, c));
    }
}
 
// This code is contributed by Samim Hossain Mondal

# Python3 implementation for the above approach
 
# Function to count possible number of strings
# such that each string consists of atleast
# 2 different characters of length 3
def countStrings(a, b, c) :
 
    # Array to store the 3 frequencies
    arr = [0]*3;
 
    arr[0] = a;
    arr[1] = b;
    arr[2] = c;
 
    # Total number of strings that can be
    # formed irrespective of the given
    # condition i.e, neglecting the condition
    # that each string consists of atleast 2
    # different characters of length 3
    count = (arr[0] + arr[1] + arr[2]) // 3;
 
    # Sort the array
    arr.sort();
 
    # If the sum of smallest and 2nd largest
    # element is less than the count, then
    # assign the sum to count
    if (arr[0] + arr[1] < count) :
        count = arr[0] + arr[1];
 
    # Return the count
    return count;
 
# Driver Code
if __name__ == "__main__" :
 
    a = 5; b = 4; c = 3;
 
    print(countStrings(a, b, c));
 
    # This code is contributed by AnkThon

// C# code for the above approach
using System;
 
public class GFG
{
   
    // Function to count possible number of strings
    // such that each string consists of atleast
    // 2 different characters of length 3
    public static int countStrings(int a, int b, int c)
    {
 
        // Array to store the 3 frequencies
        int[] arr = new int[3];
 
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
 
        // Total number of strings that can be
        // formed irrespective of the given
        // condition i.e, neglecting the condition
        // that each string consists of atleast 2
        // different characters of length 3
        int count = (arr[0] + arr[1] + arr[2]) / 3;
 
        // Sort the array
        Array.Sort(arr);
 
        // If the sum of smallest and 2nd largest
        // element is less than the count, then
        // assign the sum to count
        if (arr[0] + arr[1] < count) {
            count = arr[0] + arr[1];
        }
 
        // Return the count
        return count;
    }
 
    // Driver Code
    static public void Main()
    {
 
        // Code
        int a = 5, b = 4, c = 3;
 
        Console.Write(countStrings(a, b, c));
    }
}
 
// This code is contributed by Potta Lokesh

<script>
 
// Javascript implementation for the above approach
 
// Function to count possible number of strings
// such that each string consists of atleast
// 2 different characters of length 3
function countStrings(a, b, c)
{
    // Array to store the 3 frequencies
    var arr = [0,0,0];
 
    arr[0] = a;
    arr[1] = b;
    arr[2] = c;
 
    // Total number of strings that can be
    // formed irrespective of the given
    // condition i.e, neglecting the condition
    // that each string consists of atleast 2
    // different characters of length 3
    var count = parseInt((arr[0] + arr[1] + arr[2]) / 3);
 
    // Sort the array
    arr.sort((a,b) => a-b);
 
    // If the sum of smallest and 2nd largest
    // element is less than the count, then
    // assign the sum to count
    if (arr[0] + arr[1] < count) {
        count = arr[0] + arr[1];
    }
 
    // Return the count
    return count;
}
 
// Driver Code
var a = 5, b = 4, c = 3;
document.write(countStrings(a, b, c));
 
// This code is contributed by rutvik_56.
</script>

4

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)