Maximice el valor de String asignando valores en el rango [1, 26] a cada carácter

Posted on by Rudeus Greyrat

Dada una string S de tamaño N , la tarea es encontrar la suma máxima de valores asignados a todos los alfabetos de la string S. El valor asignado a todos los caracteres está por encima del rango [1, 26] , y los valores asignados al mismo carácter en minúsculas y mayúsculas son los mismos.

Ejemplos:

Entrada: S = “pQrqQPR”
Salida: 176
Explicación:
El valor de la letra ‘P’ se toma como 25, ‘Q’ se toma como 26, ‘R’ se toma como 24. Ahora, la suma de los valores asignados a la caracteres de la string es 25 + 26 + 24 + 26 + 26 + 25 + 24 = 176, que es el máximo entre todas las combinaciones posibles de asignación de valores.

Entrada: S = “#aAaa$”
Salida: 104

Enfoque: el problema dado se puede resolver almacenando la frecuencia de los alfabetos en una array de frecuencia y clasificándolos en orden descendente . La idea es multiplicar la frecuencia más alta por 26 , la segunda frecuencia más alta por 25 , y así sucesivamente. Siga los pasos a continuación para resolver el problema dado:

  • Inicialice una array auxiliar, por ejemplo, frecuencia[] que almacena la frecuencia de distintos caracteres en la string S .
  • Atraviese la string y en cada iteración, si el carácter ch , luego incremente la frecuencia usando los siguientes casos:
    • Mayúsculas: incrementa el valor en la frecuencia [ch – ‘A’] .
    • Minúsculas: incrementa el valor en la frecuencia [ch – ‘a’] .
    • Carácter especial: continúa el ciclo .
  • Ordene la array de frecuencias [] en orden creciente.
  • Inicialice una variable, diga suma como 0 para almacenar el valor de la string.
  • Recorra la array en orden inverso usando una variable i del índice 25 al 0 , y en cada iteración realice los siguientes pasos:
    • Si el valor en la frecuencia[i] es 0 , rompa el bucle .
    • De lo contrario, multiplique el valor de frecuencia[i] con i y súmelo a la variable suma .
  • Después de los pasos anteriores, imprima el valor de la suma como resultado.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find max possible sum
// of values assigned to each characters
// of the given string
int maxStrength(string s)
{
    // Initialize a frequency array of
    // size 26 with all elements as 0
    vector<int> frequency(26, 0);
 
    for (char ch : s) {
 
        // Lowercase character
        if (ch >= 'a' && ch <= 'z') {
            frequency[ch - 'a']++;
        }
 
        // Uppercase character
        else if (ch >= 'A' && ch <= 'Z') {
            frequency[ch - 'A']++;
        }
    }
 
    // Sort the frequency array
    sort(frequency.begin(),
         frequency.end());
 
    // Stores the maximum sum of value
    int ans = 0;
 
    for (int i = 25; i >= 0; i--) {
 
        // If the frequency of the
        // current character is > 0
        if (frequency[i] > 0) {
            ans = ans + frequency[i] * (i + 1);
        }
 
        // Otherwise
        else
            break;
    }
 
    // Return the maximum sum obtained
    return ans;
}
 
// Driver Code
int main()
{
    string S = "pQrqQPR";
    cout << maxStrength(S);
 
    return 0;
}

Java

// java program for the above approach
 
import java.util.*;
 
public class GFG {
     
    // Function to find max possible sum
    // of values assigned to each characters
    // of the given string
    static int maxStrength(String s)
    {
        // Initialize a frequency array of
        // size 26 with all elements as 0
        int []frequency = new int[26];
        int len = s.length();
     
        for (int i = 0; i < len; i++){
     
            char ch = s.charAt(i);
             
            // Lowercase character
            if (ch >= 'a' && ch <= 'z') {
                frequency[ch - 'a']++;
            }
     
            // Uppercase character
            else if (ch >= 'A' && ch <= 'Z') {
                frequency[ch - 'A']++;
            }
        }
     
        // Sort the frequency array
        Arrays.sort(frequency);
     
        // Stores the maximum sum of value
        int ans = 0;
     
        for (int i = 25; i >= 0; i--) {
     
            // If the frequency of the
            // current character is > 0
            if (frequency[i] > 0) {
                ans = ans + frequency[i] * (i + 1);
            }
     
            // Otherwise
            else
                break;
        }
     
        // Return the maximum sum obtained
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args) {
        String S = "pQrqQPR";
        System.out.println(maxStrength(S));
    }
}
 
// This code is contributed by AnkThon

Python3

#  python program for the above approach
 
# Function to find max possible sum
#  of values assigned to each characters
#  of the given string
def maxStrength(s):
   
    # Initialize a frequency array of
    # size 26 with all elements as 0
    frequency = [0 for x in range(26)]
    for ch in s:
       
        # Lowercase character
        if (ch >= 'a' and ch <= 'z'):
            frequency[ord(ch)-97] += 1
 
        # Uppercase character
        elif (ch >= 'A' and ch <= 'Z'):
            frequency[ord(ch)-65] += 1
 
    # Sort the frequency array
    frequency.sort()
 
    # Stores the maximum sum of value
    ans = 0
    for i in range(25, 0, -1):
       
        # If the frequency of the
        # current character is > 0
        if (frequency[i] > 0):
            ans = ans + frequency[i] * (i + 1)
 
        # Otherwise
        else:
            break
 
    # Return the maximum sum obtained
    return ans
 
# Driver Code
S = "pQrqQPR"
print(maxStrength(S))
 
# This code is contributed by amrshkumar3.

C#

// C# program for the above approach
using System;
 
public class GFG
{
 
    // Function to find max possible sum
    // of values assigned to each characters
    // of the given string
    static int maxStrength(string s)
    {
       
        // Initialize a frequency array of
        // size 26 with all elements as 0
        int []frequency = new int[26];
        int len = s.Length;
     
        for (int i = 0; i < len; i++){
     
            char ch = s[i];
             
            // Lowercase character
            if (ch >= 'a' && ch <= 'z') {
                frequency[ch - 'a']++;
            }
     
            // Uppercase character
            else if (ch >= 'A' && ch <= 'Z') {
                frequency[ch - 'A']++;
            }
        }
     
        // Sort the frequency array
        Array.Sort(frequency);
     
        // Stores the maximum sum of value
        int ans = 0;
     
        for (int i = 25; i >= 0; i--) {
     
            // If the frequency of the
            // current character is > 0
            if (frequency[i] > 0) {
                ans = ans + frequency[i] * (i + 1);
            }
     
            // Otherwise
            else
                break;
        }
     
        // Return the maximum sum obtained
        return ans;
    }
 
// Driver Code
public static void Main(String[] args)
{
    string S = "pQrqQPR";
    Console.Write(maxStrength(S));
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
      // JavaScript Program to implement
      // the above approach
 
      // Function to find max possible sum
      // of values assigned to each characters
      // of the given string
      function maxStrength(s)
      {
       
          // Initialize a frequency array of
          // size 26 with all elements as 0
          let frequency = new Array(26).fill(0);
 
          for (let ch of s) {
 
              // Lowercase character
              if (ch.charCodeAt(0) >= 'a'.charCodeAt(0) && ch.charCodeAt(0) <= 'z'.charCodeAt(0)) {
                  frequency[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
              }
 
              // Uppercase character
              else if (ch.charCodeAt(0) >= 'A'.charCodeAt(0) && ch.charCodeAt(0) <= 'Z'.charCodeAt(0)) {
                  frequency[ch.charCodeAt(0) - 'A'.charCodeAt(0)]++;
              }
          }
 
          // Sort the frequency array
          frequency.sort(function (a, b) { return a - b })
 
          // Stores the maximum sum of value
          let ans = 0;
 
          for (let i = 25; i >= 0; i--) {
 
              // If the frequency of the
              // current character is > 0
              if (frequency[i] > 0) {
                  ans = ans + frequency[i] * (i + 1);
              }
 
              // Otherwise
              else
                  break;
          }
 
          // Return the maximum sum obtained
          return ans;
      }
 
      // Driver Code
      let S = "pQrqQPR";
      document.write(maxStrength(S));
 
  // This code is contributed by Potta Lokesh
  </script>
Producción: 

176

 

Complejidad de tiempo: O(N* log N)
Espacio auxiliar: O(26)

Publicación traducida automáticamente

Artículo escrito por sushilsekhar300 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *