Maximiza el costo obtenido al eliminar las substrings «pr» o «rp» de una String dada

Posted on by Rudeus Greyrat

Dada una string str y dos enteros X e Y , la tarea es encontrar el costo máximo requerido para eliminar todas las substrings «pr» y «rp» de la string dada, donde la eliminación de las substrings «rp» y «pr» cuesta X e Y respectivamente.

Ejemplos:

Entrada: str = “abppprrr”, X = 5, Y = 4 
Salida: 15 
Explicación: 
Se realizan las siguientes operaciones: 
“abpp pr rr” -> “abpprr”, costo = 5 
“abp pr r” -> “abpr”, costo = 10 
“ab pr ” -> “ab”, costo = 15 
Por lo tanto, el costo maximizado es 15

Entrada: str = “prprprrp”, X = 7, Y = 10 
Salida: 37

Enfoque : El problema se puede resolver usando el Enfoque Codicioso . La idea aquí es eliminar «pr» si X es mayor que Y o eliminar «rp» de lo contrario. Siga los pasos a continuación para resolver el problema.

  1. Si X <Y: Intercambie el valor de X e Y y reemplace el carácter ‘p’ por ‘r’ y viceversa en la string dada.
  2. Inicialice dos variables countP y countR para almacenar el recuento de ‘p’ y ‘r’ en la string respectivamente.
  3. Iterar sobre la array arr[] y realizar los pasos a continuación: 
    • Si str[i] = ‘p’: Incrementa el conteoP en 1.
    • Si str[i] = ‘r’: compruebe el valor de countP . Si countP > 0 , entonces incremente el resultado en X y disminuya el valor de countP en 1. De lo contrario, incremente el valor de countR en 1.
    • Si str[i] != ‘p’ y str[i]!=’r’: Incremente el resultado en min(countP, countR) * Y .
  4. Incremente el resultado por min(countP, countR) * Y .
  5. Finalmente, después de eliminar todas las substrings requeridas, imprima el resultado obtenido.

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to maintain the case, X>=Y
bool swapXandY(string& str, int X, int Y)
{
 
    int N = str.length();
 
    // To maintain X>=Y
    swap(X, Y);
 
    for (int i = 0; i < N; i++) {
 
        // Replace 'p' to 'r'
        if (str[i] == 'p') {
            str[i] = 'r';
        }
 
        // Replace 'r' to 'p'.
        else if (str[i] == 'r') {
            str[i] = 'p';
        }
    }
}
 
// Function to return the maximum cost
int maxCost(string str, int X, int Y)
{
    // Stores the length of the string
    int N = str.length();
 
    // To maintain X>=Y.
    if (Y > X) {
        swapXandY(str, X, Y);
    }
 
    // Stores the maximum cost
    int res = 0;
 
    // Stores the count of 'p'
    // after removal of all "pr"
    // substrings up to str[i]
    int countP = 0;
 
    // Stores the count of 'r'
    // after removal of all "pr"
    // substrings up to str[i]
    int countR = 0;
 
    // Stack to maintain the order of
    // characters after removal of
    // substrings
    for (int i = 0; i < N; i++) {
 
        if (str[i] == 'p') {
            countP++;
        }
        else if (str[i] == 'r') {
 
            // If substring "pr"
            // is removed
            if (countP > 0) {
                countP--;
 
                // Increase cost by X
                res += X;
            }
            else
                countR++;
        }
        else {
 
            // If any substring "rp"
            // left in the Stack
            res += min(countP, countR) * Y;
            countP = 0;
            countR = 0;
        }
    }
 
    // If any substring "rp"
    // left in the Stack
    res += min(countP, countR) * Y;
    return res;
}
 
// Driver Code
int main()
{
    string str = "abppprrr";
    int X = 5, Y = 4;
    cout << maxCost(str, X, Y);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to maintain the case, X>=Y
static boolean swapXandY(char []str, int X, int Y)
{
    int N = str.length;
 
    // To maintain X>=Y
    X = X + Y;
    Y = X - Y;
    X = X - Y;
 
    for(int i = 0; i < N; i++)
    {
 
        // Replace 'p' to 'r'
        if (str[i] == 'p')
        {
            str[i] = 'r';
        }
 
        // Replace 'r' to 'p'.
        else if (str[i] == 'r')
        {
            str[i] = 'p';
        }
    }
    return true;
}
 
// Function to return the maximum cost
static int maxCost(String str, int X, int Y)
{
     
    // Stores the length of the String
    int N = str.length();
 
    // To maintain X>=Y.
    if (Y > X)
    {
        swapXandY(str.toCharArray(), X, Y);
    }
 
    // Stores the maximum cost
    int res = 0;
 
    // Stores the count of 'p'
    // after removal of all "pr"
    // subStrings up to str[i]
    int countP = 0;
 
    // Stores the count of 'r'
    // after removal of all "pr"
    // subStrings up to str[i]
    int countR = 0;
 
    // Stack to maintain the order of
    // characters after removal of
    // subStrings
    for(int i = 0; i < N; i++)
    {
        if (str.charAt(i) == 'p')
        {
            countP++;
        }
        else if (str.charAt(i) == 'r')
        {
             
            // If subString "pr"
            // is removed
            if (countP > 0)
            {
                countP--;
 
                // Increase cost by X
                res += X;
            }
            else
                countR++;
        }
        else
        {
 
            // If any subString "rp"
            // left in the Stack
            res += Math.min(countP, countR) * Y;
            countP = 0;
            countR = 0;
        }
    }
 
    // If any subString "rp"
    // left in the Stack
    res += Math.min(countP, countR) * Y;
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "abppprrr";
    int X = 5, Y = 4;
     
    System.out.print(maxCost(str, X, Y));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Function to maintain the case, X>=Y
def swapXandY(str, X, Y):
 
    N = len(str)
 
    # To maintain X>=Y
    X, Y = Y, X
 
    for i in range(N):
 
        # Replace 'p' to 'r'
        if(str[i] == 'p'):
            str[i] = 'r'
 
        # Replace 'r' to 'p'.
        elif(str[i] == 'r'):
            str[i] = 'p'
 
# Function to return the maximum cost
def maxCost(str, X, Y):
 
    # Stores the length of the string
    N = len(str)
 
    # To maintain X>=Y.
    if(Y > X):
        swapXandY(str, X, Y)
 
    # Stores the maximum cost
    res = 0
 
    # Stores the count of 'p'
    # after removal of all "pr"
    # substrings up to str[i]
    countP = 0
 
    # Stores the count of 'r'
    # after removal of all "pr"
    # substrings up to str[i]
    countR = 0
 
    # Stack to maintain the order of
    # characters after removal of
    # substrings
    for i in range(N):
        if(str[i] == 'p'):
            countP += 1
 
        elif(str[i] == 'r'):
 
            # If substring "pr"
            # is removed
            if(countP > 0):
                countP -= 1
 
                # Increase cost by X
                res += X
 
            else:
                countR += 1
 
        else:
             
            # If any substring "rp"
            # left in the Stack
            res += min(countP, countR) * Y
            countP = 0
            countR = 0
 
    # If any substring "rp"
    # left in the Stack
    res += min(countP, countR) * Y
 
    return res
 
# Driver Code
str = "abppprrr"
X = 5
Y = 4
 
# Function call
print(maxCost(str, X, Y))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to maintain the case, X>=Y
static bool swapXandY(char []str,
                      int X, int Y)
{
    int N = str.Length;
 
    // To maintain X>=Y
    X = X + Y;
    Y = X - Y;
    X = X - Y;
 
    for(int i = 0; i < N; i++)
    {
        // Replace 'p' to 'r'
        if (str[i] == 'p')
        {
            str[i] = 'r';
        }
 
        // Replace 'r' to 'p'.
        else if (str[i] == 'r')
        {
            str[i] = 'p';
        }
    }
    return true;
}
 
// Function to return the
// maximum cost
static int maxCost(String str,
                   int X, int Y)
{   
    // Stores the length of the String
    int N = str.Length;
 
    // To maintain X>=Y.
    if (Y > X)
    {
        swapXandY(str.ToCharArray(),
                  X, Y);
    }
 
    // Stores the maximum cost
    int res = 0;
 
    // Stores the count of 'p'
    // after removal of all "pr"
    // subStrings up to str[i]
    int countP = 0;
 
    // Stores the count of 'r'
    // after removal of all "pr"
    // subStrings up to str[i]
    int countR = 0;
 
    // Stack to maintain the order of
    // characters after removal of
    // subStrings
    for(int i = 0; i < N; i++)
    {
        if (str[i] == 'p')
        {
            countP++;
        }
        else if (str[i] == 'r')
        {           
            // If subString "pr"
            // is removed
            if (countP > 0)
            {
                countP--;
 
                // Increase cost by X
                res += X;
            }
            else
                countR++;
        }
        else
        {
            // If any subString "rp"
            // left in the Stack
            res += Math.Min(countP,
                            countR) * Y;
            countP = 0;
            countR = 0;
        }
    }
 
    // If any subString "rp"
    // left in the Stack
    res += Math.Min(countP,
                    countR) * Y;
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    String str = "abppprrr";
    int X = 5, Y = 4;   
    Console.Write(maxCost(str, X, Y));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for the
// above approach
 
// Function to maintain the case, X>=Y
function swapXandY(str, X, Y)
{
    let N = str.length;
  
    // To maintain X>=Y
    X = X + Y;
    Y = X - Y;
    X = X - Y;
  
    for(let i = 0; i < N; i++)
    {
  
        // Replace 'p' to 'r'
        if (str[i] == 'p')
        {
            str[i] = 'r';
        }
  
        // Replace 'r' to 'p'.
        else if (str[i] == 'r')
        {
            str[i] = 'p';
        }
    }
    return true;
}
  
// Function to return the maximum cost
function maxCost(str, X, Y)
{
      
    // Stores the length of the String
    let N = str.length;
  
    // To maintain X>=Y.
    if (Y > X)
    {
        swapXandY(str.split(''), X, Y);
    }
  
    // Stores the maximum cost
    let res = 0;
  
    // Stores the count of 'p'
    // after removal of all "pr"
    // subStrings up to str[i]
    let countP = 0;
  
    // Stores the count of 'r'
    // after removal of all "pr"
    // subStrings up to str[i]
    let countR = 0;
  
    // Stack to maintain the order of
    // characters after removal of
    // subStrings
    for(let i = 0; i < N; i++)
    {
        if (str[i] == 'p')
        {
            countP++;
        }
        else if (str[i] == 'r')
        {
              
            // If subString "pr"
            // is removed
            if (countP > 0)
            {
                countP--;
  
                // Increase cost by X
                res += X;
            }
            else
                countR++;
        }
        else
        {
  
            // If any subString "rp"
            // left in the Stack
            res += Math.min(countP, countR) * Y;
            countP = 0;
            countR = 0;
        }
    }
  
    // If any subString "rp"
    // left in the Stack
    res += Math.min(countP, countR) * Y;
    return res;
}
  
// Driver Code
 
    let str = "abppprrr";
    let X = 5, Y = 4;
      
    document.write(maxCost(str, X, Y));
 
// This code is contributed by target_2.
</script>
Producción: 

15

Complejidad de tiempo: O(N), donde N denota la longitud de la string
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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