Elimine los caracteres mínimos de la string para dividirla en tres substrings bajo las restricciones dadas

Posted on by Rudeus Greyrat

Dada una string str de alfabetos en minúsculas, la tarea es eliminar el mínimo de caracteres de la string dada para que la string se pueda dividir en 3 substrings str1 , str2 y str3 de modo que cada substring pueda estar vacía o puede contener solo caracteres ‘a’ , ‘b’ y ‘c’ respectivamente.
Ejemplo: 
 

Entrada: str = “aaaabaaxccac” 
Salida: 3 
Explicación: 
String después de eliminar b, x y a, entonces, la string str se convierte en “aaaaaaccc” 
Ahora str1 = “aaaaaa”, str2 = “”, str3 = “ccc”. 
El carácter mínimo eliminado es 3.
Entrada: str = «baabcbbdcca» 
Salida: 4 
Explicación: 
String después de eliminar b, c, d y a, entonces, la string str se convierte en «aabbbcc» 
Ahora str1 = «aa», str2 = «bbb» , str3 = “cc”. 
El carácter mínimo eliminado es 4. 
 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . Usaremos una array de tres prefijos para hacer una array de prefijos de los caracteres ‘a’, ‘b’ y ‘c’ . Cada array de prefijos almacenará el recuento de las letras ‘a’, ‘b’ y ‘c’ en cualquier índice i respectivamente. A continuación se muestran los pasos:
 

  1. Cree una array de tres prefijos como: 
    • pref a [i] representa el recuento de la letra «a» en el prefijo de longitud i.
    • pref b [i] representa el recuento de la letra «b» en el prefijo de longitud i.
    • pref c [i] representa el recuento de la letra «c» en el prefijo de longitud i.
  2. Para eliminar el número mínimo de caracteres, la string resultante debe tener el tamaño máximo.
  3. La idea es fijar dos posiciones i y j en la string, 0 ? i ? j ≤ N , para dividir la string en tres partes de toda la longitud posible y hacer lo siguiente: 
    • Elimine todos los caracteres excepto ‘a’ del prefijo, que termina en i, esta será la string str1 .
    • Elimine todos los caracteres excepto ‘c’ del sufijo, que comienza en j, esta será la string str3 .
    • Elimine todos los caracteres excepto ‘b’ que se encuentra entre las posiciones i y j, esta será la string str2 .
  4. Por lo tanto, la longitud total de la string resultante viene dada por: 
     

longitud total de (str1 + str2 + str3) = (prefa[i]) + (prefb[j] – prefb[i]) + (prefc[n] – prefc[j]) 
 

  1. Reste la longitud de la string resultante de la longitud de la string dada str para eliminar el mínimo de caracteres.

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 that counts minimum
// character that must be removed
void min_remove(string str)
{
    // Length of string
    int N = str.length();
 
    // Create prefix array
    int prefix_a[N + 1];
    int prefix_b[N + 1];
    int prefix_c[N + 1];
 
    // Initialize first position
    prefix_a[0] = 0;
    prefix_b[0] = 0;
    prefix_c[0] = 0;
 
    // Fill prefix array
    for (int i = 1; i <= N; i++) {
        prefix_a[i]
            = prefix_a[i - 1]
              + (str[i - 1] == 'a');
 
        prefix_b[i]
            = prefix_b[i - 1]
              + (str[i - 1] == 'b');
 
        prefix_c[i]
            = prefix_c[i - 1]
              + (str[i - 1] == 'c');
    }
 
    // Initialise maxi
    int maxi = INT_MIN;
 
    // Check all the possibilities by
    // putting i and j at different
    // position & find maximum among them
    for (int i = 0; i <= N; i++) {
 
        for (int j = i; j <= N; j++) {
 
            maxi = max(maxi,
                       (prefix_a[i]
                        + (prefix_b[j]
                           - prefix_b[i])
                        + (prefix_c[N]
                           - prefix_c[j])));
        }
    }
 
    // Print the characters to be removed
    cout << (N - maxi) << endl;
}
 
// Driver Code
int main()
{
    // Given String
    string str = "aaaabaaxccac";
 
    // Function Call
    min_remove(str);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function that counts minimum
// character that must be removed
static void min_remove(String str)
{
     
    // Length of string
    int N = str.length();
 
    // Create prefix array
    int []prefix_a = new int[N + 1];
    int []prefix_b = new int[N + 1];
    int []prefix_c = new int[N + 1];
 
    // Initialize first position
    prefix_a[0] = 0;
    prefix_b[0] = 0;
    prefix_c[0] = 0;
 
    // Fill prefix array
    for(int i = 1; i <= N; i++)
    {
        prefix_a[i] = prefix_a[i - 1] +
                     (int)((str.charAt(
                            i - 1) == 'a') ? 1 : 0);
 
        prefix_b[i] = prefix_b[i - 1] +
                      (int)((str.charAt(i - 1) ==
                                     'b') ? 1 : 0);
 
        prefix_c[i] = prefix_c[i - 1] +
                      (int)((str.charAt(i - 1) ==
                                     'c') ? 1 : 0);
    }
 
    // Initialise maxi
    int maxi = Integer.MIN_VALUE;
 
    // Check all the possibilities by
    // putting i and j at different
    // position & find maximum among them
    for(int i = 0; i <= N; i++)
    {
        for(int j = i; j <= N; j++)
        {
            maxi = Math.max(maxi, (prefix_a[i] +
                                  (prefix_b[j] -
                                   prefix_b[i]) +
                                  (prefix_c[N] -
                                   prefix_c[j])));
        }
    }
 
    // Print the characters to be removed
    System.out.println((N - maxi));
}
 
// Driver Code
public static void main(String []args)
{
     
    // Given String
    String str = "aaaabaaxccac";
 
    // Function call
    min_remove(str);
}
}
 
// This code is contributed by grand_master

Python3

# Python 3 program for the above approach
import sys
 
# Function that counts minimum
# character that must be removed
def min_remove(st):
 
    # Length of string
    N = len(st)
 
    # Create prefix array
    prefix_a = [0]*(N + 1)
    prefix_b = [0]*(N + 1)
    prefix_c = [0]*(N + 1)
 
    # Initialize first position
    prefix_a[0] = 0
    prefix_b[0] = 0
    prefix_c[0] = 0
 
    # Fill prefix array
    for i in range(1, N + 1):
         
        if (st[i - 1] == 'a'):
            prefix_a[i] = (prefix_a[i - 1] + 1)
        else:
            prefix_a[i] = prefix_a[i - 1]
 
        if (st[i - 1] == 'b'):
            prefix_b[i] = (prefix_b[i - 1] + 1)
        else:
            prefix_b[i]= prefix_b[i - 1]
 
        if (st[i - 1] == 'c'):
            prefix_c[i] = (prefix_c[i - 1] + 1)
        else:
            prefix_c[i] = prefix_c[i - 1]
     
    # Initialise maxi
    maxi = -sys.maxsize -1;
 
    # Check all the possibilities by
    # putting i and j at different
    # position & find maximum among them
    for i in range( N + 1):
        for j in range(i, N + 1):
            maxi = max(maxi,
                      (prefix_a[i] +
                      (prefix_b[j] -
                       prefix_b[i]) +
                      (prefix_c[N] -
                       prefix_c[j])))
 
    # Print the characters to be removed
    print((N - maxi))
 
# Driver Code
if __name__ == "__main__":
     
    # Given String
    st = "aaaabaaxccac"
 
    # Function Call
    min_remove(st)
 
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function that counts minimum
// character that must be removed
static void min_remove(string str)
{
     
    // Length of string
    int N = str.Length;
 
    // Create prefix array
    int []prefix_a = new int[N + 1];
    int []prefix_b = new int[N + 1];
    int []prefix_c = new int[N + 1];
 
    // Initialize first position
    prefix_a[0] = 0;
    prefix_b[0] = 0;
    prefix_c[0] = 0;
 
    // Fill prefix array
    for(int i = 1; i <= N; i++)
    {
        prefix_a[i] = prefix_a[i - 1] +
                    (int)((str[i - 1] == 'a') ?
                                   1 : 0);
 
        prefix_b[i] = prefix_b[i - 1] +
                    (int)((str[i - 1] == 'b') ?
                                   1 : 0);
 
        prefix_c[i] = prefix_c[i - 1] +
                    (int)((str[i - 1] == 'c') ?
                                   1 : 0);
    }
 
    // Initialise maxi
    int maxi = Int32.MinValue;
 
    // Check all the possibilities by
    // putting i and j at different
    // position & find maximum among them
    for(int i = 0; i <= N; i++)
    {
        for(int j = i; j <= N; j++)
        {
            maxi = Math.Max(maxi, (prefix_a[i] +
                                  (prefix_b[j] -
                                   prefix_b[i]) +
                                  (prefix_c[N] -
                                   prefix_c[j])));
        }
    }
 
    // Print the characters to be removed
    Console.WriteLine((N - maxi));
}
 
// Driver Code
public static void Main()
{
     
    // Given String
    string str = "aaaabaaxccac";
 
    // Function call
    min_remove(str);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function that counts minimum
// character that must be removed
function min_remove(str)
{
       
    // Length of string
    let N = str.length;
   
    // Create prefix array
    let prefix_a = Array.from({length: N + 1}, (_, i) => 0);
    let prefix_b = Array.from({length: N + 1}, (_, i) => 0);
    let prefix_c = Array.from({length: N + 1}, (_, i) => 0);
   
    // Initialize first position
    prefix_a[0] = 0;
    prefix_b[0] = 0;
    prefix_c[0] = 0;
   
    // Fill prefix array
    for(let i = 1; i <= N; i++)
    {
        prefix_a[i] = prefix_a[i - 1] +
                     ((str[
                            i - 1] == 'a') ? 1 : 0);
   
        prefix_b[i] = prefix_b[i - 1] +
                      ((str[i - 1] ==
                                     'b') ? 1 : 0);
   
        prefix_c[i] = prefix_c[i - 1] +
                      ((str[i - 1] ==
                                     'c') ? 1 : 0);
    }
   
    // Initialise maxi
    let maxi = Number.MIN_VALUE;
   
    // Check all the possibilities by
    // putting i and j at different
    // position & find maximum among them
    for(let i = 0; i <= N; i++)
    {
        for(let j = i; j <= N; j++)
        {
            maxi = Math.max(maxi, (prefix_a[i] +
                                  (prefix_b[j] -
                                   prefix_b[i]) +
                                  (prefix_c[N] -
                                   prefix_c[j])));
        }
    }
   
    // Print the characters to be removed
    document.write((N - maxi));
}
 
// Driver code
 
     // Given String
    let str = "aaaabaaxccac";
   
    // Function call
    min_remove(str);
 
// This code is contributed by code_hunt.
</script>
Producción: 

3

 

Complejidad de tiempo: O(N 2 ) , donde N es la longitud de la string dada. 
Complejidad espacial: O(N) , donde N es la longitud de la string dada.
 

Publicación traducida automáticamente

Artículo escrito por rutvik_56 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 *