Cuente los reemplazos mínimos de caracteres necesarios para que la string dada satisfaga las condiciones dadas

Dada una string S de longitud N que consiste en letras minúsculas, la tarea es contar el número mínimo de caracteres que deben reemplazarse para hacer que la string S sea especial.

Una string S es especial si y solo si para todos los pares posibles (S[i], S[j]) ( indexación basada en 1 ) donde 1 ≤ i ≤ N/2 y N/2 + 1 ≤ j ≤ N , uno de la siguiente condición debe ser verdadera:

• S[i] < S[j]: para los índices (i, j), cada carácter de la mitad izquierda ( S[i] ) es menor que cada carácter de la mitad derecha ( S[j] ).
• S[i] > S[j]: para el índice (i, j), cada carácter de la mitad izquierda ( S[i] ) es mayor que cada carácter de la mitad derecha ( S[j] ).
• S[i] = S[j]: para el índice (i, j), cada carácter de la mitad izquierda ( S[i] ) es igual a cada carácter de la mitad derecha ( S[j] ).

Ejemplos:

Entrada: S = “aababc“ 
Salida: 2
Explicación:
La parte izquierda y derecha de la string son Left= “aab”, Right=”abc” 
Operación 1: Cambiar s[4] → d
Operación 2: Cambiar s[5] → d
Después de aplicar los cambios anteriores, la string resultante es «aabddc» que satisface todas las condiciones para una string especial.

Entrada: S = “aabaab” 
Salida: 2
Explicación:
La parte izquierda y derecha de la string son Left=”aab” Right=”aab”
Operación 1:  Cambiar s[3] → a
Operación 2:  Cambiar s[6] → a
Después de aplicar los cambios anteriores, la string resultante es «aaaaaa» que satisface todas las condiciones para una string especial.

Enfoque: La idea es observar que solo hay 26 alfabetos. El número de cambios para s[i]==s[j] se puede hacer usando el conteo de la frecuencia de los caracteres . Siga los pasos a continuación para resolver el problema anterior:

• Almacene la frecuencia de los caracteres de la mitad izquierda y derecha en la array izquierda [] y derecha [] respectivamente.
• Inicialice un recuento de variables para realizar un seguimiento del número mínimo de cambios que se realizarán.
• Recorra el rango [0, 26] usando la variable d y cambie los caracteres según los casos a continuación:
  • Para s[i] igual a s[j]: haga que todos los caracteres sean iguales a un carácter c, luego el valor de conteo es   (N – izquierda – derecha) .
  • Para s[i] menor que s[j]:
    • Inicialmente, con el número máximo de cambios, haga en el lado izquierdo, deje que los cambios sean N/2 .
    • Reste todos los caracteres en el lado izquierdo que son ≤ d para encontrar los caracteres restantes para cambiar.
    • Agregue todos los caracteres en el lado derecho que son iguales a d para cambiar aquellos caracteres que son mayores que d como cambio -= izquierda y cambio += derecha .
  • Para s[i] mayor que s[j]:
    • Inicialmente, con el número máximo de cambios, haga en el lado derecho, deje que el cambio sea N/2 .
    • Reste todos los caracteres en el lado derecho que son ≤d para encontrar los caracteres restantes para cambiar.
    • Agregue todos los caracteres en el lado izquierdo que son iguales a d para cambiar esos caracteres a > d. (s[i]<s[j]) como cambio += izquierda y cambio -= derecha .
• El mínimo de todos los conteos en los casos anteriores es el resultado requerido.

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 that finds the minimum
// count of steps required to make
// the string special
int minChange(string s, int n)
{
     
    // Stores the frequency of the
    // left & right half of string
    int L[26] = {0};
    int R[26] = {0};
     
    // Find frequency of left half
    for(int i = 0; i < n / 2; i++)
    {
        char ch = s[i];
        L[ch - 'a']++;
    }
     
    // Find frequency of left half
    for(int i = n / 2; i < n; i++)
    {
        char ch = s[i];
        R[ch - 'a']++;
    }
     
    int count = n;
     
    // Make all characters equal
    // to character c
    for(char ch = 'a'; ch <= 'z'; ch++)
    {
        count = min(count,
                    n - L[ch - 'a'] -
                        R[ch - 'a']);
    }
     
    // Case 1: For s[i] < s[j]
    int change = n / 2;
    for(int d = 0; d + 1 < 26; d++)
    {
         
        // Subtract all the characters
        // on left side that are <=d
        change -= L[d];
         
        // Adding all characters on the
        // right side that same as d
        change += R[d];
         
        // Find minimum value of count
        count = min(count, change);
    }
     
    // Similarly for Case 2: s[i] > s[j]
    change = n / 2;
     
    for(int d = 0; d + 1 < 26; d++)
    {
        change -= R[d];
        change += L[d];
        count = min(change, count);
    }
     
    // Return the minimum changes
    return count;
}
 
// Driver Code
int main()
{
     
    // Given string S
    string S = "aababc";
 
    int N = S.length();
 
    // Function Call
    cout << minChange(S, N) << "\n";
}
 
// This code is contributed by sallagondaavinashreddy7

// Java program for the above approach
 
import java.io.*;
import java.util.*;
class Main {
 
    // Function that finds the minimum
    // count of steps required to make
    // the string special
    public static int minChange(String s,
                                int n)
    {
 
        // Stores the frequency of the
        // left & right half of string
        int L[] = new int[26];
        int R[] = new int[26];
 
        // Find frequency of left half
        for (int i = 0; i < n / 2; i++) {
            char ch = s.charAt(i);
            L[ch - 'a']++;
        }
 
        // Find frequency of left half
        for (int i = n / 2; i < n; i++) {
            char ch = s.charAt(i);
            R[ch - 'a']++;
        }
        int count = n;
 
        // Make all characters equal
        // to character c
        for (char ch = 'a'; ch <= 'z'; ch++) {
 
            count = Math.min(
                count,
                n - L[ch - 'a']
                    - R[ch - 'a']);
        }
 
        // Case 1: For s[i] < s[j]
        int change = n / 2;
        for (int d = 0; d + 1 < 26; d++) {
 
            // Subtract all the characters
            // on left side that are <=d
            change -= L[d];
 
            // Adding all characters on the
            // right side that same as d
            change += R[d];
 
            // Find minimum value of count
            count = Math.min(count, change);
        }
 
        // Similarly for Case 2: s[i] > s[j]
        change = n / 2;
 
        for (int d = 0; d + 1 < 26; d++) {
            change -= R[d];
            change += L[d];
            count = Math.min(change, count);
        }
 
        // Return the minimum changes
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string S
        String S = "aababc";
 
        int N = S.length();
 
        // Function Call
        System.out.println(minChange(S, N));
    }
}

# Python3 program for the
# above approach
 
# Function that finds the minimum
# count of steps required to make
# the string special
def minChange (s, n):
 
    # Stores the frequency of the
    # left & right half of string
    L = [0] * 26;
    R = [0] * 26;
 
    # Find frequency of left half
    for i in range(0, n // 2):
        ch = s[i];
        L[ord(ch) -
          ord('a')] += 1;
 
    # Find frequency of left half
    for i in range(n // 2, n):
        ch = s[i];
        R[ord(ch) -
          ord('a')] += 1;
 
    count = n;
 
    # Make all characters equal
    # to character c
    for ch in range(ord('a'),
                    ord('z')):
        count = min(count, n - L[ch - ord('a')] -
                               R[ch - ord('a')]);
 
    # Case 1: For s[i] < s[j]
    change = n / 2;
     
    for d in range(0, 25):
       
        # Subtract all the characters
        # on left side that are <=d
        change -= L[d];
 
        # Adding all characters on the
        # right side that same as d
        change += R[d];
 
        # Find minimum value of count
        count = min(count, change);
 
    # Similarly for Case 2: s[i] > s[j]
    change = n / 2;
 
    for d in range(0, 25):
        change -= R[d];
        change += L[d];
        count = min(change, count);
 
    # Return the minimum changes
    return int(count);
 
# Driver Code
if __name__ == '__main__':
   
    # Given string S
    S = "aababc";
 
    N = len(S);
 
    # Function Call
    print(minChange(S, N));
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
 
class GFG{
     
// Function that finds the minimum
// count of steps required to make
// the string special
public static int minChange(String s,
                            int n)
{
     
    // Stores the frequency of the
    // left & right half of string
    int []L = new int[26];
    int []R = new int[26];
 
    // Find frequency of left half
    for(int i = 0; i < n / 2; i++)
    {
        char ch = s[i];
        L[ch - 'a']++;
    }
 
    // Find frequency of left half
    for(int i = n / 2; i < n; i++)
    {
        char ch = s[i];
        R[ch - 'a']++;
    }
    int count = n;
 
    // Make all characters equal
    // to character c
    for(char ch = 'a'; ch <= 'z'; ch++)
    {
        count = Math.Min(count,
                         n - L[ch - 'a'] -
                             R[ch - 'a']);
    }
 
    // Case 1: For s[i] < s[j]
    int change = n / 2;
    for(int d = 0; d + 1 < 26; d++)
    {
         
        // Subtract all the characters
        // on left side that are <=d
        change -= L[d];
         
        // Adding all characters on the
        // right side that same as d
        change += R[d];
 
        // Find minimum value of count
        count = Math.Min(count, change);
    }
 
    // Similarly for Case 2: s[i] > s[j]
    change = n / 2;
 
    for(int d = 0; d + 1 < 26; d++)
    {
        change -= R[d];
        change += L[d];
        count = Math.Min(change, count);
    }
 
    // Return the minimum changes
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given string S
    String S = "aababc";
     
    int N = S.Length;
     
    // Function Call
    Console.WriteLine(minChange(S, N));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
      // JavaScript program for the above approach
       
      // Function that finds the minimum
      // count of steps required to make
      // the string special
      function minChange(s, n)
      {
        // Stores the frequency of the
        // left & right half of string
        var L = new Array(26).fill(0);
        var R = new Array(26).fill(0);
 
        // Find frequency of left half
        for (var i = 0; i < n / 2; i++) {
          var ch = s[i].charCodeAt(0);
          L[ch - "a".charCodeAt(0)]++;
        }
 
        // Find frequency of left half
        for (var i = n / 2; i < n; i++) {
          var ch = s[i].charCodeAt(0);
          R[ch - "a".charCodeAt(0)]++;
        }
        var count = n;
 
        // Make all characters equal
        // to character c
        for (var ch = "a".charCodeAt(0);
        ch <= "z".charCodeAt(0); ch++) {
          count = Math.min(
            count,
            n - L[ch - "a".charCodeAt(0)] -
            R[ch - "a".charCodeAt(0)]
          );
        }
 
        // Case 1: For s[i] < s[j]
        var change = parseInt(n / 2);
        for (var d = 0; d + 1 < 26; d++) {
          // Subtract all the characters
          // on left side that are <=d
          change -= L[d];
 
          // Adding all characters on the
          // right side that same as d
          change += R[d];
 
          // Find minimum value of count
          count = Math.min(count, change);
        }
 
        // Similarly for Case 2: s[i] > s[j]
        change = n / 2;
 
        for (var d = 0; d + 1 < 26; d++) {
          change -= R[d];
          change += L[d];
          count = Math.min(change, count);
        }
 
        // Return the minimum changes
        return count;
      }
 
      // Driver Code
      // Given string S
      var S = "aababc";
      var N = S.length;
 
      // Function Call
      document.write(minChange(S, N));
       
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)