Haga que todos los caracteres de una string sean iguales por un número mínimo de incrementos o decrementos de valores ASCII de caracteres

Dada una string S de longitud N , la tarea es hacer que todos los caracteres de la string sean iguales incrementando/disminuyendo el valor ASCII de cualquier carácter en 1 cualquier número de veces. 
Nota: Todos los caracteres deben cambiarse a un carácter de la string original.

Ejemplos:

Entrada: S = “geeks”
Salida: 20
Explicación:
El número mínimo de operaciones puede lograrse haciendo que todos los caracteres de la string sean iguales a ‘g’.
Incremente el valor ASCII de 2 ‘e’s en 2.
Disminuya el valor ASCII de ‘k’ en 4,  
Disminuya el valor ASCII de ‘s’ en 12.
Por lo tanto, el número de operaciones requeridas = 2 + 2 + 4 + 12 = 20

Entrada: S = “pastel”
Salida: 12
Explicación: 
El número mínimo de operaciones se puede lograr haciendo que todos los caracteres de la string sean iguales a ‘c’.
Incremente el valor ASCII de ‘a’ en 2.
Disminuya el valor ASCII de ‘e’ en 2.
Disminuya el valor ASCII de ‘k’ en 8.
Por lo tanto, el número de operaciones requeridas = 2 + 2 + 8 = 12

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la string y, para cada carácter distinto, calcular el número total de operaciones requeridas para hacer que todos los caracteres de la string sean iguales a ese carácter. Finalmente, imprima el número mínimo de operaciones requeridas para cualquier carácter. 
Complejidad temporal: O(N ² )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar haciendo una observación de que el número mínimo de operaciones se puede lograr solo si los caracteres se igualan al carácter mediano en una string ordenada. 
Siga los pasos a continuación para resolver el problema:

• Ordena los caracteres de la string en orden no decreciente .
• Ahora, para hacer que todos los caracteres sean iguales con un número mínimo de operaciones, haga que los caracteres sean iguales al carácter en el medio de la string ordenada.
• Encuentre el carácter en el medio de la string ordenada como mid = S[N / 2] .
• Inicialice una variable, digamos total_operations , para almacenar la cantidad mínima de operaciones requeridas para hacer que todos los caracteres de la string sean iguales.
• Recorra la string y, para cada carácter encontrado, actualice total_operations agregando la diferencia absoluta del carácter actual y mid .
• Imprime total_operations como el número mínimo de operaciones requeridas.

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 check if all characters
// of the string can be made the same
int sameChar(string S, int N)
{
 
    // Sort the string
    sort(S.begin(), S.end());
 
    // Calculate ASCII value
    // of the median character
    int mid = S[N / 2];
 
    // Stores the minimum number of
    // operations required to make
    // all characters equal
    int total_operations = 0;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
        // Calculate absolute value of
        // current character and median character
        total_operations
            += abs(int(S[i]) - mid);
    }
 
    // Print the minimum number of
    // operations required
    cout << total_operations;
}
 
// Driver Code
int main()
{
    string S = "geeks";
    int N = S.size();
 
    sameChar(S, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG {
 
  // Function to check if all characters
  // of the string can be made the same
  static void sameChar(String S, int N)
  {
 
    char temp[] = S.toCharArray();
 
    // Sort the string
    Arrays.sort(temp);
 
    String s = new String(temp);
 
    // Calculate ASCII value
    // of the median character
    int mid = s.charAt(N / 2);
 
    // Stores the minimum number of
    // operations required to make
    // all characters equal
    int total_operations = 0;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
      // Calculate absolute value of
      // current character and median character
      total_operations
        += Math.abs(((s.charAt(i) - 0) - mid));
    }
 
    // Print the minimum number of
    // operations required
    System.out.print(total_operations);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String S = "geeks";
    int N = S.length();
 
    sameChar(S, N);
  }
}
 
// This code is contributed by Dharanendra L V.

# Python program for the above approach
 
# Function to check if all characters
# of the string can be made the same
def sameChar(S, N):
 
    # Sort the string
    S = ''.join(sorted(S))
 
    # Calculate ASCII value
    # of the median character
    mid = ord(S[N // 2])
 
    # Stores the minimum number of
    # operations required to make
    # all characters equal
    total_operations = 0
 
    # Traverse the string
    for i in range(N):
 
        # Calculate absolute value of
        # current character and median character
        total_operations += abs(ord(S[i]) - mid)
 
    # Print the minimum number of
    # operations required
    print(total_operations)
 
# Driver Code
S = "geeks"
N = len(S)
sameChar(S, N)
 
# This code is contributed by subhammahato348.

// C# program for the above approach
using System;
public class GFG {
 
  // Function to check if all characters
  // of the string can be made the same
  static void sameChar(String S, int N)
  {
 
    char[] temp = S.ToCharArray();
 
    // Sort the string
    Array.Sort(temp);
 
    String s = new String(temp);
 
    // Calculate ASCII value
    // of the median character
    int mid = s[N / 2];
 
    // Stores the minimum number of
    // operations required to make
    // all characters equal
    int total_operations = 0;
 
    // Traverse the string
    for (int i = 0; i < N; i++) {
 
      // Calculate absolute value of
      // current character and median character
      total_operations += Math.Abs((s[i] - 0) - mid);
    }
 
    // Print the minimum number of
    // operations required
    Console.Write(total_operations);
  }
 
  // Driver Code
  static public void Main()
  {
 
    String S = "geeks";
    int N = S.Length;
 
    sameChar(S, N);
  }
}
 
// This code is contributed by Dharanendra L V.

<script>
      // JavaScript program for the above approach
      // Function to check if all characters
      // of the string can be made the same
      function sameChar(S, N) {
        // Sort the string
        var arr = S.split("");
        var sorted = arr.sort();
        S = sorted.join("");
 
        // Calculate ASCII value
        // of the median character
        var mid = S[parseInt(N / 2)].charCodeAt(0);
 
        // Stores the minimum number of
        // operations required to make
        // all characters equal
        var total_operations = 0;
 
        // Traverse the string
        for (var i = 0; i < N; i++) {
          // Calculate absolute value of
          // current character and median character
          total_operations += Math.abs(S[i].charCodeAt(0) - mid);
        }
 
        // Print the minimum number of
        // operations required
        document.write(total_operations);
      }
 
      // Driver Code
      var S = "geeks";
      var N = S.length;
      sameChar(S, N);
    </script>

20

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