Dada una string str , la tarea es verificar si es posible dividir la string dada en substrings palindrómicas de longitud uniforme .
Ejemplos:
Entrada: str = “abbacc”
Salida: Sí
Explicación: Las
strings “abba” y “cc” son las substrings palindrómicas de longitud par.
Entrada: str = “abcde”
Salida: No
Explicación:
No son posibles substrings palindrómicas de longitud uniforme.
Enfoque: La idea es utilizar Stack Data Structure . A continuación se muestran los pasos:
- Inicializar una pila vacía.
- Atraviesa la string dada str .
- Para cada carácter en la string dada, haga lo siguiente:
- Si el carácter es igual al carácter en la parte superior de la pila, extraiga el elemento superior de la pila.
- De lo contrario, empuje el carácter actual a la pila.
- Si la pila está vacía después de los pasos anteriores, la string dada se puede dividir en una substring palindrómica de longitud uniforme.
- De lo contrario, la string dada no se puede dividir en una substring palindrómica de longitud uniforme.
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 string str can be
// split a string into even length
// palindromic substrings
bool check(string s, int n)
{
// Initialize a stack
stack<char> st;
// Iterate the string
for (int i = 0; i < n; i++) {
// If the i-th character is same
// as that at the top of the stack
// then pop the top element
if (!st.empty() && st.top() == s[i])
st.pop();
// Else push the current character
// into the stack
else
st.push(s[i]);
}
// If the stack is empty, then even
// palindromic substrings are possible
if (st.empty()) {
return true;
}
// Else not-possible
else {
return false;
}
}
// Driver Code
int main()
{
// Given string
string str = "aanncddc";
int n = str.length();
// Function Call
if (check(str, n)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check String str can be
// split a String into even length
// palindromic subStrings
static boolean check(String s, int n)
{
// Initialize a stack
Stack<Character> st = new Stack<Character>();
// Iterate the String
for(int i = 0; i < n; i++)
{
// If the i-th character is same
// as that at the top of the stack
// then pop the top element
if (!st.isEmpty() &&
st.peek() == s.charAt(i))
st.pop();
// Else push the current character
// into the stack
else
st.add(s.charAt(i));
}
// If the stack is empty, then even
// palindromic subStrings are possible
if (st.isEmpty())
{
return true;
}
// Else not-possible
else
{
return false;
}
}
// Driver Code
public static void main(String[] args)
{
// Given String
String str = "aanncddc";
int n = str.length();
// Function Call
if (check(str, n))
{
System.out.print("Yes" + "\n");
}
else
{
System.out.print("No" + "\n");
}
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach
# Function to check string str can be
# split a string into even length
# palindromic substrings
def check(s, n):
st = []
# Iterate the string
for i in range(n):
# If the i-th character is same
# as that at the top of the stack
# then pop the top element
if (len(st) != 0 and
st[len(st) - 1] == s[i]):
st.pop();
# Else push the current character
# into the stack
else:
st.append(s[i]);
# If the stack is empty, then even
# palindromic substrings are possible
if (len(st) == 0):
return True;
# Else not-possible
else:
return False;
# Driver Code
# Given string
str = "aanncddc";
n = len(str)
# Function Call
if (check(str, n)):
print("Yes")
else:
print("No")
# This code is contributed by grand_master
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check String str can be
// split a String into even length
// palindromic subStrings
static bool check(String s, int n)
{
// Initialize a stack
Stack<int> st = new Stack<int>();
// Iterate the String
for(int i = 0; i < n; i++)
{
// If the i-th character is same
// as that at the top of the stack
// then pop the top element
if (st.Count != 0 &&
st.Peek() == s[i])
st.Pop();
// Else push the current character
// into the stack
else
st.Push(s[i]);
}
// If the stack is empty, then even
// palindromic subStrings are possible
if (st.Count == 0)
{
return true;
}
// Else not-possible
else
{
return false;
}
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String str = "aanncddc";
int n = str.Length;
// Function call
if (check(str, n))
{
Console.Write("Yes" + "\n");
}
else
{
Console.Write("No" + "\n");
}
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program for the above approach
// Function to check string str can be
// split a string into even length
// palindromic substrings
function check(s, n)
{
// Initialize a stack
var st = [];
// Iterate the string
for (var i = 0; i < n; i++) {
// If the i-th character is same
// as that at the top of the stack
// then pop the top element
if (st.length!=0 && st[st.length-1] == s[i])
st.pop();
// Else push the current character
// into the stack
else
st.push(s[i]);
}
// If the stack is empty, then even
// palindromic substrings are possible
if (st.length==0) {
return true;
}
// Else not-possible
else {
return false;
}
}
// Driver Code
// Given string
var str = "aanncddc";
var n = str.length;
// Function Call
if (check(str, n)) {
document.write( "Yes" );
}
else {
document.write( "No" );
}
</script>
Producción:
Yes
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar la expresión.
Espacio auxiliar: O(N), ya que estamos usando stack para espacio extra.
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA