Dada una string S y los números enteros P y Q , que denotan el costo de eliminar las substrings «ab» y «ba» respectivamente de S , la tarea es encontrar el costo máximo de eliminar todas las ocurrencias de las substrings «ab» y «ba». .
Ejemplos:
Entrada: S = “cbbaabbaab”, P = 6, Q = 4
Salida: 22
Explicación:
Eliminando la substring “ab” de “cbba ab baab”, la string obtenida es “cbbabaab”. Costo = 6.
Quitando la substring “ab” de “cbb ab aab ”, la string obtenida es “cbbaab”. Costo = 6.
Quitando la substring “ba” de “cb ba ab”, la string obtenida es “cbab”. Costo = 4.
Eliminando la substring “ab” de “cb ab ”, la string obtenida es “cb”. Costo = 6. Costo
total = 6 + 6 + 4 + 6 = 22Entrada: S = “bbaanaybbabd”, P = 3, Q = 5
Salida: 15
Explicación:
Eliminando la substring “ba” de “b ba anaybbabd”, la string obtenida es “banaybbabd”. Costo = 5.
Eliminando la substring “ba”, la string obtenida es “ ba naybbabd”, la string obtenida es “naybbabd”. Costo = 5.
Quitando la substring “ba” de “nayb ba bd”, la string obtenida es “naybbd”. Costo = 5. Costo
total = 5 + 5 + 5 = 15
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Atraviese la string y elimine un tipo de substring. Esto se puede hacer usando un enfoque codicioso como:
- Si P >= Q , elimine todas las apariciones de la substring «ab» y luego elimine todas las apariciones de la substring «ba».
- De lo contrario, elimine todas las apariciones de la substring «ba» y luego elimine todas las apariciones de la substring «ab».
- Se puede utilizar la estructura de datos de pila
- Inicialice nuestra string de mayor y menor costo como «ab» o «ba» según el valor de P y Q como arrays de caracteres maxstr[] y minstr[] de tamaño 2 e inicialice el costo máximo y el costo mínimo como maxp y minp respectivamente.
- Inicialice la variable, digamos costo , para almacenar el costo máximo
- Atraviese la cuerda y realice los siguientes pasos:
- Si la pila no está vacía y es la parte superior de la pila y el carácter actual forma maxstr[] , entonces abra la parte superior de la pila y agregue maxp al costo.
- De lo contrario, agregue el carácter actual a la pila.
- Atraviesa la string restante.
- Si la pila no está vacía y es la parte superior de la pila y el carácter actual forma el minstr[], entonces levante la parte superior de la pila y agregue minp al costo.
- De lo contrario, agregue el carácter actual a la pila.
- Imprime el costo como el costo máximo.
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 to find the maximum cost of
// removing substrings "ab" and "ba" from S
int MaxCollection(string S, int P, int Q)
{
// MaxStr is the substring char
// array with larger cost
char maxstr[2];
string x = (P >= Q ? "ab" : "ba");
strcpy(maxstr, x.c_str());
// MinStr is the substring char
// array with smaller cost;
char minstr[2];
x = (P >= Q ? "ba" : "ab");
strcpy(minstr, x.c_str());
// Denotes larger point
int maxp = max(P, Q);
// Denotes smaller point
int minp = min(P, Q);
// Stores cost scored
int cost = 0;
// Removing all occurrences of
// maxstr from the S
// Stack to keep track of characters
stack<char> stack1;
char s[S.length()];
strcpy(s, S.c_str());
// Traverse the string
for (auto &ch : s) {
// If the substring is maxstr
if (!stack1.empty()
&& (stack1.top() == maxstr[0]
&& ch == maxstr[1])) {
// Pop from the stack
stack1.pop();
// Add maxp to cost
cost += maxp;
}
// Push the character to the stack
else {
stack1.push(ch);
}
}
// Remaining string after removing maxstr
string sb = "";
// Find remaining string
while (stack1.size() > 0)
{
sb = sb + stack1.top();
stack1.pop();
}
// Reversing the string
// retrieved from the stack
reverse(sb.begin(), sb.end());
// Removing all occurrences of minstr
for (auto &ch : sb) {
// If the substring is minstr
if (!stack1.empty()
&& (stack1.top() == minstr[0]
&& ch == minstr[1])) {
// Pop from the stack
stack1.pop();
// Add minp to the cost
cost += minp;
}
// Otherwise
else {
stack1.push(ch);
}
}
// Return the maximum cost
return cost;
}
int main()
{
// Input String
string S = "cbbaabbaab";
// Costs
int P = 6;
int Q = 4;
cout << MaxCollection(S, P, Q);
return 0;
}
// This code is contributed by decode2207.
Java
// Java program for the above approach:
import java.util.*;
class GFG {
// Function to find the maximum cost of
// removing substrings "ab" and "ba" from S
public static int MaxCollection(
String S, int P, int Q)
{
// MaxStr is the substring char
// array with larger cost
char maxstr[]
= (P >= Q ? "ab" : "ba").toCharArray();
// MinStr is the substring char
// array with smaller cost;
char minstr[]
= (P >= Q ? "ba" : "ab").toCharArray();
// Denotes larger point
int maxp = Math.max(P, Q);
// Denotes smaller point
int minp = Math.min(P, Q);
// Stores cost scored
int cost = 0;
// Removing all occurrences of
// maxstr from the S
// Stack to keep track of characters
Stack<Character> stack1 = new Stack<>();
char[] s = S.toCharArray();
// Traverse the string
for (char ch : s) {
// If the substring is maxstr
if (!stack1.isEmpty()
&& (stack1.peek() == maxstr[0]
&& ch == maxstr[1])) {
// Pop from the stack
stack1.pop();
// Add maxp to cost
cost += maxp;
}
// Push the character to the stack
else {
stack1.push(ch);
}
}
// Remaining string after removing maxstr
StringBuilder sb = new StringBuilder();
// Find remaining string
while (!stack1.isEmpty())
sb.append(stack1.pop());
// Reversing the string
// retrieved from the stack
sb = sb.reverse();
String remstr = sb.toString();
// Removing all occurrences of minstr
for (char ch : remstr.toCharArray()) {
// If the substring is minstr
if (!stack1.isEmpty()
&& (stack1.peek() == minstr[0]
&& ch == minstr[1])) {
// Pop from the stack
stack1.pop();
// Add minp to the cost
cost += minp;
}
// Otherwise
else {
stack1.push(ch);
}
}
// Return the maximum cost
return cost;
}
// Driver Code
public static void main(String[] args)
{
// Input String
String S = "cbbaabbaab";
// Costs
int P = 6;
int Q = 4;
System.out.println(MaxCollection(S, P, Q));
}
}
Python3
# Python3 program for the above approach:
# Function to find the maximum cost of
# removing substrings "ab" and "ba" from S
def MaxCollection(S, P, Q):
# MaxStr is the substring char
# array with larger cost
maxstr = [i for i in ("ab" if P >= Q else "ba")]
# MinStr is the substring char
# array with smaller cost;
minstr = [i for i in ("ba" if P >= Q else "ab")]
# Denotes larger point
maxp = max(P, Q)
# Denotes smaller point
minp = min(P, Q)
# Stores cost scored
cost = 0
# Removing all occurrences of
# maxstr from the S
# Stack to keep track of characters
stack1 = []
s = [i for i in S]
# Traverse the string
for ch in s:
# If the substring is maxstr
if (len(stack1)>0 and (stack1[-1] == maxstr[0] and ch == maxstr[1])):
# Pop from the stack
del stack1[-1]
# Add maxp to cost
cost += maxp
# Push the character to the stack
else:
stack1.append(ch)
# Remaining string after removing maxstr
sb = ""
# Find remaining string
while (len(stack1) > 0):
sb += stack1[-1]
del stack1[-1]
# Reversing the string
# retrieved from the stack
sb = sb[::-1]
remstr = sb
# Removing all occurrences of minstr
for ch in remstr:
# If the substring is minstr
if (len(stack1) > 0 and (stack1[-1] == minstr[0] and ch == minstr[1])):
# Pop from the stack
del stack1[-1]
# Add minp to the cost
cost += minp
# Otherwise
else:
stack1.append(ch)
# Return the maximum cost
return cost
# Driver Code
if __name__ == '__main__':
# Input String
S = "cbbaabbaab"
# Costs
P = 6;
Q = 4;
print(MaxCollection(S, P, Q));
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach:
using System;
using System.Collections;
class GFG {
// Function to find the maximum cost of
// removing substrings "ab" and "ba" from S
static int MaxCollection(string S, int P, int Q)
{
// MaxStr is the substring char
// array with larger cost
char[] maxstr = (P >= Q ? "ab" : "ba").ToCharArray();
// MinStr is the substring char
// array with smaller cost;
char[] minstr = (P >= Q ? "ba" : "ab").ToCharArray();
// Denotes larger point
int maxp = Math.Max(P, Q);
// Denotes smaller point
int minp = Math.Min(P, Q);
// Stores cost scored
int cost = 0;
// Removing all occurrences of
// maxstr from the S
// Stack to keep track of characters
Stack stack1 = new Stack();
char[] s = S.ToCharArray();
// Traverse the string
foreach(char ch in s) {
// If the substring is maxstr
if (stack1.Count > 0 && ((char)stack1.Peek() == maxstr[0] && ch == maxstr[1])) {
// Pop from the stack
stack1.Pop();
// Add maxp to cost
cost += maxp;
}
// Push the character to the stack
else {
stack1.Push(ch);
}
}
// Remaining string after removing maxstr
string sb = "";
// Find remaining string
while (stack1.Count > 0)
{
sb = sb + stack1.Peek();
stack1.Pop();
}
// Reversing the string
// retrieved from the stack
char[] chars = sb.ToCharArray();
Array.Reverse(chars);
string remstr = new string(chars);
// Removing all occurrences of minstr
foreach(char ch in remstr.ToCharArray()) {
// If the substring is minstr
if (stack1.Count > 0 && ((char)stack1.Peek() == minstr[0] && ch == minstr[1])) {
// Pop from the stack
stack1.Pop();
// Add minp to the cost
cost += minp;
}
// Otherwise
else {
stack1.Push(ch);
}
}
// Return the maximum cost
return cost;
}
static void Main()
{
// Input String
string S = "cbbaabbaab";
// Costs
int P = 6;
int Q = 4;
Console.Write(MaxCollection(S, P, Q));
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// JavaScript program for the above approach:
// Function to find the maximum cost of
// removing substrings "ab" and "ba" from S
function MaxCollection(S,P,Q)
{
// MaxStr is the substring char
// array with larger cost
let maxstr
= (P >= Q ? "ab" : "ba").split("");
// MinStr is the substring char
// array with smaller cost;
let minstr
= (P >= Q ? "ba" : "ab").split("");
// Denotes larger point
let maxp = Math.max(P, Q);
// Denotes smaller point
let minp = Math.min(P, Q);
// Stores cost scored
let cost = 0;
// Removing all occurrences of
// maxstr from the S
// Stack to keep track of characters
let stack1 = [];
let s = S.split("");
// Traverse the string
for (let ch=0;ch< s.length;ch++) {
// If the substring is maxstr
if (stack1.length!=0
&& (stack1[stack1.length-1] == maxstr[0]
&& s[ch] == maxstr[1])) {
// Pop from the stack
stack1.pop();
// Add maxp to cost
cost += maxp;
}
// Push the character to the stack
else {
stack1.push(s[ch]);
}
}
// Remaining string after removing maxstr
let sb = [];
// Find remaining string
while (stack1.length!=0)
sb.push(stack1.pop());
// Reversing the string
// retrieved from the stack
sb = sb.reverse();
let remstr = sb.join("");
// Removing all occurrences of minstr
for (let ch =0;ch<remstr.length;ch++) {
// If the substring is minstr
if (stack1.length!=0
&& (stack1[stack1.length-1] == minstr[0]
&& remstr[ch] == minstr[1])) {
// Pop from the stack
stack1.pop();
// Add minp to the cost
cost += minp;
}
// Otherwise
else {
stack1.push(remstr[ch]);
}
}
// Return the maximum cost
return cost;
}
// Driver Code
// Input String
let S = "cbbaabbaab";
// Costs
let P = 6;
let Q = 4;
document.write(MaxCollection(S, P, Q));
// This code is contributed by patel2127
</script>
Producción:
22
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(N), ya que se ha tomado N espacio extra.