Dados dos enteros positivos X e Y y dos strings numéricas S y P de longitud N y 2 respectivamente, la tarea es encontrar el costo total máximo obtenido al eliminar repetidamente la string P o el reverso de la string P de la string S al costo de X e Y respectivamente.
Ejemplos:
Entrada: S = «12333444», X = 5, Y = 4, P = «34»
Salida: 15
Explicación:
A continuación se muestran las operaciones para eliminar la substring para obtener el costo máximo:
- Retire la string « 34″ de la string S. Por lo tanto, la string S se modifica a «123344». Costo = 5.
- Retire la string « 34″ de la string S. Por lo tanto, la string S se modifica a «1234». Costo = 5.
- Retire la string « 34″ de la string S. Por lo tanto, la string S se modifica a «12». Costo = 5.
Por lo tanto, el costo total es 5 + 5 + 5 = 15.
Entrada: S = “12121221”, X = 7, Y = 10, P = “12”
Salida: 37
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso y la pila . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 para almacenar el costo máximo de eliminar las substrings dadas.
- Inicialice una pila que se utiliza para decidir si se elimina la string P o el reverso de P.
- Atraviese la string S dada y realice los siguientes pasos:
- Si el carácter actual y el carácter superior no son iguales a P[1] y P[0] respectivamente o si la pila está vacía, empuje el carácter actual en la pila .
- De lo contrario, elimine el elemento superior de la pila e incremente el valor y por X .
- De manera similar, el reverso de la string P se puede eliminar de cualquier string agregando Y al costo.
- Ahora, si X es mayor que Y , entonces quitar P antes de quitar el reverso de P dará un valor mayor. De lo contrario, retire primero el reverso del patrón P.
- Después de completar los pasos anteriores, imprima el valor de ans como el costo máximo total.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Initialize amount
int ans[1] = {0};
// Function to remove reverse of P first
void rp(string str, int x, int y, bool flag, char p, char r)
{
// Initialize empty stack
stack<char>stk;
// Iterate through each char in string
for(int i = 0; i < str.length(); i++)
{
// Remove reverse of P
if (str[i]== p) {
if (stk.size() > 0 && stk.top() == r)
{
ans[0] += y;
// Pop the element from
// the stack
stk.pop();
}
else
{
stk.push(str[i]);
}
}
else
{
stk.push(str[i]);
}
// Remove P, if needed
ans[0]+=1;
if (flag)
{
string s = "";
stack<char> s1 ;
while (s1.size() > 0) {
s += s1.top();
s1.pop();
}
pr(s, x, y, false, p, r);
}
}
}
// Function to remove the string P first
void pr(string str, int x, int y, bool flag, char p, char r) {
// Initialize empty stack
stack<int>stk;
// Iterate through each char
// in string
for(int i = 0; i < str.length(); i++) {
// Remove the string P
if (str[i]== r) {
if (stk.size() > 0 && stk.top() == p) {
ans[0] += x;
stk.pop();
}
// If no such pair exists just
// push the chars to stack
else {
stk.push(str[i]);
}
}
else {
stk.push(str[i]);
}
ans[0] += 1;
// Remove reverse of P, if needed
if (flag) {
string s = "";
stack<char>s1;
while (s1.size() > 0) {
s = s + s1.top();
s1.pop();
}
rp(s, x, y, false, p, r);
}
}
}
// Function to find the appropriate answer
int solve(string str, int x, int y, char p, char r) {
// Remove P then reverse of P
if (x > y)
pr(str, x, y, true, p, r);
// Remove reverse of P then P
else
rp(str, x, y, true, p, r);
// Return the result
return ans[0]-1;
}
// Driver Code
int main() {
// Given string S
string S = "12333444";
// Given X and Y
int x = 5;
int y = 4;
// Given P
String P = "34";
// Function Call
cout<<solve(S, x, y, P[0], P[1]<<endl;
return 0;
}
// This code is contributed by dwivediyash
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Initialize amount
static int[] ans = {0};
// Function to remove the string P first
static void pr(String str, int x, int y, boolean flag, char p, char r) {
// Initialize empty stack
Stack<Character> stack = new Stack<Character>();
// Iterate through each char
// in string
for(int i = 0; i < str.length(); i++) {
// Remove the string P
if (str.charAt(i) == r) {
if (stack.size() > 0 && stack.peek() == p) {
ans[0] += x;
stack.pop();
}
// If no such pair exists just
// push the chars to stack
else {
stack.push(str.charAt(i));
}
}
else {
stack.push(str.charAt(i));
}
ans[0] += 1;
// Remove reverse of P, if needed
if (flag) {
String s = "";
Stack<Character> s1 = stack;
while (s1.size() > 0) {
s = s + s1.peek();
s1.pop();
}
rp(s, x, y, false, p, r);
}
}
}
// Function to remove reverse of P first
static void rp(String str, int x, int y, boolean flag, char p, char r)
{
// Initialize empty stack
Stack<Character> stack = new Stack<Character>();
// Iterate through each char in string
for(int i = 0; i < str.length(); i++)
{
// Remove reverse of P
if (str.charAt(i) == p) {
if (stack.size() > 0 && stack.peek() == r)
{
ans[0] += y;
// Pop the element from
// the stack
stack.pop();
}
else
{
stack.push(str.charAt(i));
}
}
else
{
stack.push(str.charAt(i));
}
// Remove P, if needed
ans[0]+=1;
if (flag)
{
String s = "";
Stack<Character> s1 = stack;
while (s1.size() > 0) {
s = s + s1.peek();
s1.pop();
}
pr(s, x, y, false, p, r);
}
}
}
// Function to find the appropriate answer
static int solve(String str, int x, int y, char p, char r) {
// Remove P then reverse of P
if (x > y)
pr(str, x, y, true, p, r);
// Remove reverse of P then P
else
rp(str, x, y, true, p, r);
// Return the result
return ans[0]-1;
}
// Driver code
public static void main(String[] args)
{
// Given string S
String S = "12333444";
// Given X and Y
int x = 5;
int y = 4;
// Given P
String P = "34";
// Function Call
System.out.print(solve(S, x, y, P.charAt(0), P.charAt(1)));
}
}
// This code is contributed by mukesh07.
Python3
# Python program for the above approach
# Function to remove reverse of P first
def rp(string, x, y, ans, flag, p, r):
# Initialize empty stack
stack = []
# Iterate through each char in string
for char in string:
# Remove reverse of P
if char == p:
if stack and stack[-1] == r:
ans[0] += y
# Pop the element from
# the stack
stack.pop()
else:
stack.append(char)
else:
stack.append(char)
# Remove P, if needed
if flag:
pr("".join(stack), x, y, ans, False, p, r)
# Function to remove the string P first
def pr(string, x, y, ans, flag, p, r):
# Initialize empty stack
stack = []
# Iterate through each char
# in string
for char in string:
# Remove the string P
if char == r:
if stack and stack[-1] == p:
ans[0] += x
stack.pop()
# If no such pair exists just
# push the chars to stack
else:
stack.append(char)
else:
stack.append(char)
# Remove reverse of P, if needed
if flag:
rp("".join(stack), x, y, ans, False, p, r)
# Function to find the appropriate answer
def solve(string, x, y, p, r):
# Initialize amount
ans = [0]
# Remove P then reverse of P
if x > y:
pr(string, x, y, ans, True, p, r)
# Remove reverse of P then P
else:
rp(string, x, y, ans, True, p, r)
# Return the result
return ans[0]
# Driver Code
# Given string S
S = "12333444"
# Given X and Y
x = 5
y = 4
# Given P
P = "34"
# Function Call
print(solve(S, x, y, P[0], P[1]))
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Initialize amount
static int[] ans = {0};
// Function to remove the string P first
static void pr(string str, int x, int y, bool flag, char p, char r) {
// Initialize empty stack
Stack stack = new Stack();
// Iterate through each char
// in string
foreach(char c in str) {
// Remove the string P
if (c == r) {
if (stack.Count > 0 && (char)stack.Peek() == p) {
ans[0] += x;
stack.Pop();
}
// If no such pair exists just
// push the chars to stack
else {
stack.Push(c);
}
}
else {
stack.Push(c);
}
ans[0]+=1;
// Remove reverse of P, if needed
if (flag) {
string s = "";
Stack s1 = stack;
while (s1.Count > 0) {
s = s + (char)s1.Peek();
s1.Pop();
}
rp(s, x, y, false, p, r);
}
}
}
// Function to remove reverse of P first
static void rp(string str, int x, int y, bool flag, char p, char r)
{
// Initialize empty stack
Stack stack = new Stack();
// Iterate through each char in string
foreach(char c in str)
{
// Remove reverse of P
if (c == p) {
if (stack.Count > 0 && (char)stack.Peek() == r)
{
ans[0] += y;
// Pop the element from
// the stack
stack.Pop();
}
else
{
stack.Push(c);
}
}
else
{
stack.Push(c);
}
// Remove P, if needed
ans[0]+=1;
if (flag)
{
string s = "";
Stack s1 = stack;
while (s1.Count > 0) {
s = s + (char)s1.Peek();
s1.Pop();
}
pr(s, x, y, false, p, r);
}
}
}
// Function to find the appropriate answer
static int solve(string str, int x, int y, char p, char r) {
// Remove P then reverse of P
if (x > y)
pr(str, x, y, true, p, r);
// Remove reverse of P then P
else
rp(str, x, y, true, p, r);
// Return the result
return ans[0]-1;
}
static void Main()
{
// Given string S
string S = "12333444";
// Given X and Y
int x = 5;
int y = 4;
// Given P
string P = "34";
// Function Call
Console.Write(solve(S, x, y, P[0], P[1]));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to remove reverse of P first
function rp(string, x, y, ans, flag, p, r) {
// Initialize empty stack
let stack = []
// Iterate through each char in string
for (let char of string) {
// Remove reverse of P
if (char == p) {
if (stack && stack[stack.length - 1] == r) {
ans[0] += y
// Pop the element from
// the stack
stack.pop()
}
else
stack.push(char)
}
else
stack.push(char)
// Remove P, if needed
if (flag) {
pr(stack.join(""), x, y, ans, false, p, r)
}
}
}
// Function to remove the string P first
function pr(string, x, y, ans, flag, p, r) {
// Initialize empty stack
let stack = []
// Iterate through each char
// in string
for (let char of string) {
// Remove the string P
if (char == r) {
if (stack && stack[stack.length - 1] == p) {
ans[0] += x
stack.pop()
}
// If no such pair exists just
// push the chars to stack
else {
stack.push(char)
}
}
else {
stack.push(char)
}
// Remove reverse of P, if needed
if (flag) {
rp(stack.join(""), x, y, ans, false, p, r)
}
}
}
// Function to find the appropriate answer
function solve(string, x, y, p, r) {
// Initialize amount
let ans = [0]
// Remove P then reverse of P
if (x > y)
pr(string, x, y, ans, true, p, r)
// Remove reverse of P then P
else
rp(string, x, y, ans, true, p, r)
// Return the result
return ans[0]
}
// Driver Code
// Given string S
let S = "12333444"
// Given X and Y
let x = 5
let y = 4
// Given P
let P = "34"
// Function Call
document.write(solve(S, x, y, P[0], P[1]))
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
15
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por SubhamBanerjee y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA