Recuento de strings de 3 tamaños de todos los caracteres iguales o diferentes usando un total de X 0, Y 1 y Z 2

Dados tres números enteros X , Y y Z que denotan las frecuencias de tres caracteres diferentes ‘ 0 ‘, ‘ 1 ‘ y ‘2’ respectivamente. la tarea es encontrar el número máximo de strings válidas de longitud tres que se pueden formar utilizando las frecuencias dadas, de modo que en cada string los tres caracteres sean iguales o todos sean diferentes.

Ejemplos:

Entrada: X = 3, Y = 5, Z = 5
Salida : 4
Explicación : strings válidas que se pueden obtener de las frecuencias dadas: «102», «012», «111», «222».
Número de cuerdas = 4.

Entrada: X = 8, Y = 8, Z = 9
Salida: 8

Enfoque : El problema dado se puede resolver mediante las siguientes observaciones:

• Si no existen tales strings que contengan los 3 caracteres diferentes, la respuesta siempre será ( X/3 + Y/3 + Z/3 ).
• Siempre existe una solución óptima con menos de 3 strings que contengan todos los caracteres diferentes. Debido a que 3 strings de este tipo que contienen los 3 caracteres diferentes se pueden cambiar a (1 toda la string de caracteres ‘0’ + 1 toda la string de caracteres ‘1’ + 1 toda la string de caracteres ‘2’).

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 find the maximum valid
// strings that can be formed from
// the given frequencies
int maxValidStrings(int X, int Y, int Z)
{
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
        // If i is greater than any of
        // the frequencies then continue
        if (i > X || i > Y || i > Z) {
            continue;
        }
 
        // Store the remaining characters left
        int xRemain = X - i;
        int yRemain = Y - i;
        int zRemain = Z - i;
 
        // Store the maximum one
        ans = max(ans, i + (xRemain / 3)
                           + (yRemain / 3)
                           + (zRemain / 3));
    }
 
    // Return ans
    return ans;
}
 
// Driver Code
int main()
{
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    cout << maxValidStrings(X, Y, Z);
    return 0;
}

// JAVA code to implement the approach
import java.util.*;
class GFG
{
 
  // Function to find the maximum valid
  // strings that can be formed from
  // the given frequencies
  public static int maxValidStrings(int X, int Y, int Z)
  {
 
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
      // If i is greater than any of
      // the frequencies then continue
      if (i > X || i > Y || i > Z) {
        continue;
      }
 
      // Store the remaining characters left
      int xRemain = X - i;
      int yRemain = Y - i;
      int zRemain = Z - i;
 
      // Store the maximum one
      ans = Math.max(ans, i + (xRemain / 3)
                     + (yRemain / 3)
                     + (zRemain / 3));
    }
 
    // Return ans
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    System.out.print(maxValidStrings(X, Y, Z));
  }
}
 
// This code is contributed by Taranpreet

# Python code for the above approach
 
# Function to find the maximum valid
# strings that can be formed from
# the given frequencies
def maxValidStrings( X,  Y,  Z):
 
    # Variable to store the answer
    ans = 0;
    for i in range(3):
 
        # If i is greater than any of
        # the frequencies then continue
        if (i > X or i > Y or i > Z):
            continue;
         
        # Store the remaining characters left
        xRemain = X - i;
        yRemain = Y - i;
        zRemain = Z - i;
 
        # Store the maximum one
        ans = max(ans, i + (xRemain // 3)
                           + (yRemain // 3)
                           + (zRemain // 3));
     
 
    # Return ans
    return ans;
 
# Driver Code
X = 8;
Y = 8;
Z = 9;
 
    # Function call
print(maxValidStrings(X, Y, Z));
    
# This code is contributed by Potta Lokesh

// C# code to implement the approach
using System;
class GFG {
 
  // Function to find the maximum valid
  // strings that can be formed from
  // the given frequencies
  static int maxValidStrings(int X, int Y, int Z)
  {
 
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
      // If i is greater than any of
      // the frequencies then continue
      if (i > X || i > Y || i > Z) {
        continue;
      }
 
      // Store the remaining characters left
      int xRemain = X - i;
      int yRemain = Y - i;
      int zRemain = Z - i;
 
      // Store the maximum one
      ans = Math.Max(ans, i + (xRemain / 3)
                     + (yRemain / 3)
                     + (zRemain / 3));
    }
 
    // Return ans
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    Console.Write(maxValidStrings(X, Y, Z));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the approach
 
    // Function to find the maximum valid
    // strings that can be formed from
    // the given frequencies
    const maxValidStrings = (X, Y, Z) => {
     
        // Variable to store the answer
        let ans = 0;
        for (let i = 0; i < 3; i++) {
 
            // If i is greater than any of
            // the frequencies then continue
            if (i > X || i > Y || i > Z) {
                continue;
            }
 
            // Store the remaining characters left
            let xRemain = X - i;
            let yRemain = Y - i;
            let zRemain = Z - i;
 
            // Store the maximum one
            ans = Math.max(ans, i + parseInt(xRemain / 3)
                + parseInt(yRemain / 3)
                + parseInt(zRemain / 3));
        }
 
        // Return ans
        return ans;
    }
 
    // Driver Code
 
    let X = 8, Y = 8, Z = 9;
 
    // Function call
    document.write(maxValidStrings(X, Y, Z));
 
// This code is contributed by rakeshsahni
 
</script>

8

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