Dada una string S de tamaño N que consta de los caracteres ‘ a ‘, ‘ b ‘ y ‘ c ‘ solamente, la tarea es verificar si la string dada puede quedar vacía eliminando la string «abc» recursivamente o no. Si se encuentra que es cierto , escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = abcabc
Salida: Sí
Explicación:
A continuación se muestran las operaciones realizadas para vaciar la string:
- Eliminar la substring S[3, 5] de la string modifica la string S a «abc».
- Eliminar la substring S[0, 2] de la string modifica la string S a “”.
Después de las operaciones anteriores, la string S dada puede quedar vacía eliminando la substring «abc». Por lo tanto, imprima Sí.
Entrada: S = abcabcababccc
Salida: No
Enfoque: El problema dado se puede resolver usando una pila . La idea es minimizar la string a una string vacía eliminando todas las apariciones de «abc» . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una pila , diga Stack para almacenar los caracteres de la string S dada .
- Atraviese la string S dada y realice los siguientes pasos:
- Si el carácter actual es ‘ a ‘ o ‘ b ‘, entonces empújelo a la pila Stack .
- Si el carácter actual es ‘ c ‘ y los dos últimos caracteres son ‘ b ‘ y ‘ a ‘ respectivamente, salte dos veces de la pila .
- Si el carácter actual es ‘ c ‘ y los dos últimos caracteres no son ‘ b ‘ ni ‘ a ‘, entonces la string S dada no se puede formar.
- Después de completar los pasos anteriores, si la pila está vacía , imprima «Sí» . De lo contrario, escriba “No” .
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 check if the given
// string S can be made empty
string canMadeEmpty(string s, int n)
{
// Stores the characters
// of the string S
stack<char> St;
// Traverse the given string
for (int i = 0; i < n; i++) {
// If the character is c
if (s[i] == 'c') {
// If stack size is greater
// than 2
if (St.size() >= 2) {
// Pop from the stack
char b = St.top();
St.pop();
char a = St.top();
St.pop();
// Top two characters in
// the stack should be 'b'
// and 'a' respectively
if (a != 'a' || b != 'b')
return "No";
}
// Otherwise, print No
else
return "No";
}
// If character is 'a' or 'b'
// push to stack
else
St.push(s[i]);
}
// If stack is empty, then print
// Yes. Otherwise print No
if (St.size() == 0) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
int main()
{
string S = "aabcbc";
int N = S.length();
cout << canMadeEmpty(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if the given
// String S can be made empty
static String canMadeEmpty(String s, int n)
{
// Stores the characters
// of the String S
Stack<Character> St = new Stack<Character>();
// Traverse the given String
for (int i = 0; i < n; i++)
{
// If the character is c
if (s.charAt(i) == 'c') {
// If stack size is greater
// than 2
if (St.size() >= 2) {
// Pop from the stack
char b = St.peek();
St.pop();
char a = St.peek();
St.pop();
// Top two characters in
// the stack should be 'b'
// and 'a' respectively
if (a != 'a' || b != 'b')
return "No";
}
// Otherwise, print No
else
return "No";
}
// If character is 'a' or 'b'
// push to stack
else
St.add(s.charAt(i));
}
// If stack is empty, then print
// Yes. Otherwise print No
if (St.size() == 0) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
public static void main(String[] args)
{
String S = "aabcbc";
int N = S.length();
System.out.print(canMadeEmpty(S, N));
}
}
// This code is contributed by Princi Singh.
Python3
# Python program for the above approach # Function to check if the given # string S can be made empty def canMadeEmpty(s, n): # Stores the characters # of the string S st = [] # Traverse the given string for i in range(n): # If the character is c if s[i] == 'c': # If stack size is greater # than 2 if len(st) >= 2: # Pop from the stack b = st[-1] st.pop() a = st[-1] st.pop() # Top two characters in # the stack should be 'b' # and 'a' respectively if a != 'a' or b != 'b': return "No" # Otherwise, print No else: return "No" # If character is 'a' or 'b' # push to stack else: st.append(s[i]) # If stack is empty, then print # Yes. Otherwise print No if len(st) == 0: return "Yes" else: return "No" # Driver code s = "aabcbc" n = len(s) print(canMadeEmpty(s, n)) # This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check if the given
// String S can be made empty
static String canMadeEmpty(String s, int n)
{
// Stores the characters
// of the String S
Stack<char> St = new Stack<char>();
// Traverse the given String
for (int i = 0; i < n; i++)
{
// If the character is c
if (s[i] == 'c') {
// If stack size is greater
// than 2
if (St.Count >= 2) {
// Pop from the stack
char b = St.Peek();
St.Pop();
char a = St.Peek();
St.Pop();
// Top two characters in
// the stack should be 'b'
// and 'a' respectively
if (a != 'a' || b != 'b')
return "No";
}
// Otherwise, print No
else
return "No";
}
// If character is 'a' or 'b'
// push to stack
else
St.Push(s[i]);
}
// If stack is empty, then print
// Yes. Otherwise print No
if (St.Count == 0) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
public static void Main(String[] args)
{
String S = "aabcbc";
int N = S.Length;
Console.Write(canMadeEmpty(S, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program for the above approach
// Function to check if the given
// string S can be made empty
function canMadeEmpty(s, n) {
// Stores the characters
// of the string S
let St = [];
// Traverse the given string
for (let i = 0; i < n; i++) {
// If the character is c
if (s[i] == 'c') {
// If stack size is greater
// than 2
if (St.length >= 2) {
// Pop from the stack
let b = St[St.length - 1];
St.pop();
let a = St[St.length - 1];
St.pop();
// Top two characters in
// the stack should be 'b'
// and 'a' respectively
if (a != 'a' || b != 'b')
return "No";
}
// Otherwise, print No
else
return "No";
}
// If character is 'a' or 'b'
// push to stack
else
St.push(s[i]);
}
// If stack is empty, then print
// Yes. Otherwise print No
if (St.length == 0) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
let S = "aabcbc";
let N = S.length;
document.write(canMadeEmpty(S, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por krishnumkhodke y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA