Minimice las eliminaciones para reducir la string al tamaño 1 en el que con la eliminación, se pueden eliminar N/2^i ocurrencias de (X+i-1) carácter.

Posted on by Rudeus Greyrat

Dada la string str de longitud N y un carácter X , donde N siempre tiene la forma 2 k , la tarea es encontrar las operaciones de reemplazo mínimas requeridas para reducir el tamaño de la string a 1 donde i -ésima eliminación, N/2 ilas apariciones de (X + i – 1) th carácter se pueden eliminar desde el frente o el reverso de la string.

Ejemplo:

Entrada: str = “CDAAAABB”, X = ‘A’
Salida: 4
Explicación: Las operaciones de reemplazo en la string dada se pueden realizar como:

  1. Reemplace ‘C’ en el 1er índice con ‘A’.
  2. Reemplace ‘D’ en el segundo índice con ‘A’.
  3. Reemplace ‘A’ en el quinto índice con ‘D’.
  4. Reemplace ‘A’ en el sexto índice con ‘C’.

Por lo tanto, la string se convierte en str = “AAAADCBB”. Durante la primera eliminación (8/2 1 ) las apariciones de (A+1-1) el carácter pueden eliminarse del principio de la string. Por lo tanto, la string se convierte en str = «DCBB». De manera similar, durante la segunda eliminación (8/2 2 ) las apariciones de (A+2-1) ,  es decir, el carácter ‘B’ se puede eliminar de la parte posterior de la string. Por lo tanto, la string se convierte en str = «DC». De manera similar, después de la tercera eliminación, la string se convierte en str = «D» con una longitud de 1. Por lo tanto, el número de operaciones de reemplazo requeridas es 4, que es el mínimo posible.

Entrada: str = «QRQP», X = ‘P’
Salida: 1

 

Enfoque: El problema dado se puede resolver utilizando Recursión que tiene una estructura similar a la de la Búsqueda binaria . Durante cada borrado, se puede observar que hay 2 elecciones posibles. Son los siguientes:

  1. Reemplace todos los caracteres de la primera mitad de la string dada por ‘X’ y solicite recursivamente la mitad restante para X = X + 1.
  2. O reemplace todos los caracteres de la segunda mitad de la string dada por ‘X’ y llame recursivamente a la mitad restante para X = X + 1.

Por lo tanto, utilizando las observaciones anteriores, cree una función recursiva que elimine los movimientos mínimos de las dos posibilidades calculando la cantidad de índices que deben reemplazarse en X en la primera mitad de la string y llamando recursivamente a la mitad restante y viceversa .

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

C++

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find minimum
// replacements required to reduce the
// size of the given string to 1
int minReplacment(string s, char x)
{
    // Base Case
    if (s.size() == 1) {
        return s[0] != x;
    }
 
    // Stores the middle index
    int mid = s.size() / 2;
 
    // Recursive call for left half
    int cntl = minReplacment(
        string(s.begin(), s.begin() + mid), x + 1);
    cntl += s.size() / 2
            - count(s.begin() + mid, s.end(), x);
 
    // Recursive call for right half
    int cntr = minReplacment(
        string(s.begin() + mid, s.end()), x + 1);
    cntr += s.size() / 2
            - count(s.begin(), s.begin() + mid, x);
 
    // Return Answer
    return min(cntl, cntr);
}
 
// Driver Code
int main()
{
    int N = 8;
    string str = "CDAAAABB";
    char X = 'A';
 
    cout << minReplacment(str, X);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
// Java code for the above approach
import java.util.*;
 
class GFG {
    public static int count(String str, char c)
    {
        int ct = 0;
 
        for (int i = 0; i < str.length(); i++) {
            char currChar = str.charAt(i);
            if (currChar == c)
                ct += 1;
        }
 
        return ct;
    }
 
    // Recursive function to find minimum
    // replacements required to reduce the
    // size of the given string to 1
    static int minReplacment(String s, char x)
    {
        // Base Case
        if (s.length() == 1) {
            if (s.charAt(0) == x)
                return 1;
            return 0;
        }
 
        // Stores the middle index
        int mid = s.length() / 2;
 
        // Recursive call for left half
        char p = (char)(x + 1);
        int cntl = minReplacment(s.substring(0, mid), p);
        cntl = cntl + s.length() / 2
               - count(s.substring(mid, s.length()), x);
 
        // Recursive call for right half
        char t = (char)(x + 1);
        int cntr = minReplacment(
            s.substring(mid, s.length()), t);
        cntr = cntr + s.length() / 2
               - count(s.substring(0, mid), x);
 
        // Return Answer
        return Math.min(cntl + 1, cntr);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int N = 8;
        String str = "CDAAAABB";
        char X = 'A';
        System.out.println(minReplacment(str, X));
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python 3 implementation for the above approach
 
# Recursive function to find minimum
# replacements required to reduce the
# size of the given string to 1
def minReplacment(s,  x):
 
    # Base Case
    if (len(s) == 1):
        return s[0] != x
 
    # Stores the middle index
    mid = len(s) // 2
 
    # Recursive call for left half
    cntl = minReplacment(
        s[:mid], chr(ord(x) + 1))
    cntl += len(s) // 2 - s[mid:].count(x)
 
    # Recursive call for right half
    cntr = minReplacment(
        s[mid:], chr(ord(x) + 1))
    cntr += len(s) // 2 - s[:mid].count(x)
 
    # Return Answer
    return min(cntl, cntr)
 
# Driver Code
if __name__ == "__main__":
 
    N = 8
    st = "CDAAAABB"
    X = 'A'
 
    print(minReplacment(st, X))
 
    # This code is contributed by ukasp.

C#

/*package whatever //do not write package name here */
// C# code for the above approach
using System;
 
public class GFG {
    public static int count(String str, char c)
    {
        int ct = 0;
 
        for (int i = 0; i < str.Length; i++) {
            char currChar = str[i];
            if (currChar == c)
                ct += 1;
        }
 
        return ct;
    }
 
    // Recursive function to find minimum
    // replacements required to reduce the
    // size of the given string to 1
    static int minReplacment(String s, char x)
    {
        // Base Case
        if (s.Length == 1) {
            if (s[0] == x)
                return 1;
            return 0;
        }
 
        // Stores the middle index
        int mid = s.Length / 2;
 
        // Recursive call for left half
        char p = (char)(x + 1);
        int cntl = minReplacment(s.Substring(0, mid), p);
        cntl = cntl + s.Length / 2
               - count(s.Substring(mid, s.Length-mid), x);
 
        // Recursive call for right half
        char t = (char)(x + 1);
        int cntr = minReplacment(
            s.Substring(mid, s.Length-mid), t);
        cntr = cntr + s.Length / 2
               - count(s.Substring(0, mid), x);
 
        // Return Answer
        return Math.Min(cntl + 1, cntr);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String str = "CDAAAABB";
        char X = 'A';
        Console.WriteLine(minReplacment(str, X));
    }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript implementation for the above approach
 
function count(str, c) {
    let ct = 0;
 
    for (let i = 0; i < str.length; i++) {
        let currChar = str[i];
        if (currChar == c)
            ct += 1;
    }
 
    return ct;
}
 
// Recursive function to find minimum
// replacements required to reduce the
// size of the given string to 1
function minReplacment(s, x) {
    // Base Case
    if (s.length == 1) {
        if(s[0] == x){
            return 1
        }
        return 0
    }
 
    // Stores the middle index
    let mid = Math.floor(s.length / 2);
 
    // Recursive call for left half
    let cntl = minReplacment(s.substring(0, mid), String.fromCharCode(x.charCodeAt(0) + 1));
    cntl += Math.floor(s.length / 2) - count(s.substring(mid, s.length), x);
 
    // Recursive call for right half
    let cntr = minReplacment(new String(s.substring(mid, s.length)), String.fromCharCode(x.charCodeAt(0) + 1));
    cntr += Math.floor(s.length / 2) - count(s.substring(0, mid), x);
 
    // Return Answer
    return Math.min(cntl + 1, cntr);
}
 
// Driver Code
 
let N = 8;
let str = "CDAAAABB";
let X = 'A';
 
document.write(minReplacment(str, X));
 
// This code is contributed by gfgking.
</script>
Producción

4

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

Publicación traducida automáticamente

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