Given a string str, the task is to check if it is possible to split the given string into even length palindromic substrings.
Examples:
Input: str = “abbacc”
Output: Yes
Explanation:
Strings “abba” and “cc” are the even length palindromic substrings.
Input: str = “abcde”
Output: No
Explanation:
No even length palindromic substrings possible.
Approach: The idea is to use Stack Data Structure. Below are the steps:
- Initialise an empty stack.
- Traverse the given string str.
- For each character in the given string, do the following:
- If the character is equal to the character at the top of the stack then pop the top element from the stack.
- Else push the current character into the stack.
- If stack is empty after the above steps then the given string can be break into a palindromic substring of even length.
- Else the given string cannot be break into palindromic substring of even length.
Below is the implementation of the above approach:
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 substringsbool 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 Codeint 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 approachimport java.util.*;class GFG{// Function to check String str can be// split a String into even length// palindromic subStringsstatic 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 Codepublic 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 approachusing System;using System.Collections.Generic;class GFG{// Function to check String str can be// split a String into even length// palindromic subStringsstatic 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 Codepublic 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 substringsfunction 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 stringvar str = "aanncddc";var n = str.length;// Function Callif (check(str, n)) { document.write( "Yes" );}else { document.write( "No" );}</script> |
Output:
Yes
Time Complexity: O(N), as we are using a loop for traversing the expression.
Auxiliary Space: O(N), as we are using stack for extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
