Maximice las strings palindrómicas de longitud 3 posibles a partir del recuento dado de alfabetos

Dada una array arr[] de tamaño 26 , que representa frecuencias de carácter ‘a’ a ‘z’ , la tarea es encontrar el número máximo de strings palindrómicas de longitud 3 que se pueden generar a partir del recuento especificado de alfabetos.

Ejemplos:

Entrada: arr[] = {4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0}
Salida: 3
Explicación: Una de las posibles soluciones es tomar dos caracteres de ‘b’ y un carácter de ‘a’, formando la string «bab». Ahora quedan 3 ‘a’ y 3 ‘b’ a partir de los cuales se pueden formar las strings «aaa» y «bbb». Por lo tanto, se pueden formar un total de 3 cuerdas palindrómicas.

Entrada: arr[]= {2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0}
Salida: 1 
Explicación: La única string palindrómica posible es “aba”.

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

1. El número de strings se puede maximizar haciendo posible primero strings de un solo tipo de carácter.
2. Después de eso, tome dos caracteres de un tipo y un carácter del otro tipo y forme una string.
3. Si todavía existen caracteres que aparecen en más de 1, entonces tome 3 entre tales caracteres y forme 2 strings de tipo «ACA» y «BCB».
4. Si nuevamente quedan dos caracteres que ocurren 2 veces, entonces forme una string y agregue uno más para responder.
5. Después de esto, solo quedarán los caracteres que aparezcan una sola vez o un carácter que aparezca dos veces.

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

• Inicialice una variable, res con 0 para almacenar el recuento de strings palindrómicas máximas de tamaño 3 que se pueden formar.
• Inicialice una variable, C1 y C2 con 0 para almacenar el recuento de caracteres que tienen una frecuencia uno y dos respectivamente
• Itere sobre la array , arr[] e incremente la resolución en arr[i]/3 , establezca arr[i] en arr[i]%3 e incremente C1 en 1 si arr[i]%3 es 1 ; de lo contrario, incrementar C2 en 1 si arr[i]%3 es 2 .
• Después del recorrido, incremente la res por min (C1, C2) y actualice C1 y C2 . Luego, incremente res al doble de C2/3 y actualice C2 . Por último, incremente la resolución en C2/2 .
• Finalmente, imprima res como la respuesta.

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 count maximum number
// of palindromic string of length 3
void maximum_pallindromic(int arr[])
{
    // Stores the final count of
    // palindromic strings
    int res = 0;
    int c1 = 0, c2 = 0;
 
    // Traverse the array
    for (int i = 0; i < 26; i++) {
 
        // Increment res by arr[i]/3,
        // i.e forming string of
        // only i +'a' character
        res += arr[i] / 3;
 
        // Store remainder
        arr[i] = arr[i] % 3;
 
        // Increment c1 by one, if
        // current frequency is 1
        if (arr[i] == 1)
            c1++;
 
        // Increment c2 by one, if
        // current frequency is 2
        else if (arr[i] == 2)
            c2++;
    }
 
    // Count palindromic strings of
    // length 3 having the character
    // at the ends different from that
    // present in the middle
    res += min(c1, c2);
    int t = min(c1, c2);
 
    // Update c1 and c2
    c1 -= t;
    c2 -= t;
 
    // Increment res by 2 * c2/3
    res += 2 * (c2 / 3);
    c2 %= 3;
    res += c2 / 2;
 
    // Finally print the result
    cout << res;
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 4, 5, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
    // Function Call
    maximum_pallindromic(arr);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to count maximum number
// of palindromic String of length 3
static void maximum_pallindromic(int arr[])
{
   
    // Stores the final count of
    // palindromic Strings
    int res = 0;
    int c1 = 0, c2 = 0;
 
    // Traverse the array
    for (int i = 0; i < 26; i++)
    {
 
        // Increment res by arr[i]/3,
        // i.e forming String of
        // only i +'a' character
        res += arr[i] / 3;
 
        // Store remainder
        arr[i] = arr[i] % 3;
 
        // Increment c1 by one, if
        // current frequency is 1
        if (arr[i] == 1)
            c1++;
 
        // Increment c2 by one, if
        // current frequency is 2
        else if (arr[i] == 2)
            c2++;
    }
 
    // Count palindromic Strings of
    // length 3 having the character
    // at the ends different from that
    // present in the middle
    res += Math.min(c1, c2);
    int t = Math.min(c1, c2);
 
    // Update c1 and c2
    c1 -= t;
    c2 -= t;
 
    // Increment res by 2 * c2/3
    res += 2 * (c2 / 3);
    c2 %= 3;
    res += c2 / 2;
 
    // Finally print the result
    System.out.print(res);
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given array
    int arr[] = { 4, 5, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
    // Function Call
    maximum_pallindromic(arr);
}
}
 
// This code is contributed by aashish1995

# Python3 program for the above approach
 
# Function to count maximum number
# of palindromic string of length 3
def maximum_pallindromic(arr):
 
    # Stores the final count of
    # palindromic strings
    res = 0
    c1 = 0
    c2 = 0
 
    # Traverse the array
    for i in range(26):
 
        # Increment res by arr[i]/3,
        # i.e forming string of
        # only i +'a' character
        res += arr[i] // 3
 
        # Store remainder
        arr[i] = arr[i] % 3
 
        # Increment c1 by one, if
        # current frequency is 1
        if (arr[i] == 1):
            c1 += 1
 
        # Increment c2 by one, if
        # current frequency is 2
        elif (arr[i] == 2):
            c2 += 1
 
    # Count palindromic strings of
    # length 3 having the character
    # at the ends different from that
    # present in the middle
    res += min(c1, c2)
    t = min(c1, c2)
 
    # Update c1 and c2
    c1 -= t
    c2 -= t
 
    # Increment res by 2 * c2/3
    res += 2 * (c2 // 3)
    c2 %= 3
    res += c2 // 2
 
    # Finally print the result
    print(res)
 
# Driver Code
if __name__ == "__main__":
 
    # Given array
    arr = [ 4, 5, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0 ]
 
    # Function Call
    maximum_pallindromic(arr)
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
 
public class GFG
{
 
// Function to count maximum number
// of palindromic String of length 3
static void maximum_pallindromic(int []arr)
{
   
    // Stores the readonly count of
    // palindromic Strings
    int res = 0;
    int c1 = 0, c2 = 0;
 
    // Traverse the array
    for (int i = 0; i < 26; i++)
    {
 
        // Increment res by arr[i]/3,
        // i.e forming String of
        // only i +'a' character
        res += arr[i] / 3;
 
        // Store remainder
        arr[i] = arr[i] % 3;
 
        // Increment c1 by one, if
        // current frequency is 1
        if (arr[i] == 1)
            c1++;
 
        // Increment c2 by one, if
        // current frequency is 2
        else if (arr[i] == 2)
            c2++;
    }
 
    // Count palindromic Strings of
    // length 3 having the character
    // at the ends different from that
    // present in the middle
    res += Math.Min(c1, c2);
    int t = Math.Min(c1, c2);
 
    // Update c1 and c2
    c1 -= t;
    c2 -= t;
 
    // Increment res by 2 * c2/3
    res += 2 * (c2 / 3);
    c2 %= 3;
    res += c2 / 2;
 
    // Finally print the result
    Console.Write(res);
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Given array
    int []arr = { 4, 5, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0,
                  0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
    // Function Call
    maximum_pallindromic(arr);
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program for the above approach
 
// Function to count maximum number
// of palindromic string of length 3
function maximum_pallindromic(arr)
{
    // Stores the final count of
    // palindromic strings
    var res = 0;
    var c1 = 0, c2 = 0;
 
    // Traverse the array
    for (var i = 0; i < 26; i++) {
 
        // Increment res by arr[i]/3,
        // i.e forming string of
        // only i +'a' character
        res += parseInt(arr[i] / 3);
 
        // Store remainder
        arr[i] = (arr[i] % 3);
 
        // Increment c1 by one, if
        // current frequency is 1
        if (arr[i] == 1)
            c1++;
 
        // Increment c2 by one, if
        // current frequency is 2
        else if (arr[i] == 2)
            c2++;
    }
 
    // Count palindromic strings of
    // length 3 having the character
    // at the ends different from that
    // present in the middle
    res += Math.min(c1, c2);
    var t = Math.min(c1, c2);
 
    // Update c1 and c2
    c1 -= t;
    c2 -= t;
 
    // Increment res by 2 * c2/3
    res += 2 * parseInt(c2 / 3);
    c2 %= 3;
    res += parseInt(c2 / 2);
 
    // Finally print the result
    document.write( res);
}
 
// Driver Code
// Given array
var arr = [ 4, 5, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0 ];
// Function Call
maximum_pallindromic(arr);
 
</script>

3

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