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> |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/check-if-a-string-can-be-split-into-even-length-palindromic-substrings/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/check-if-a-string-can-be-split-into-even-length-palindromic-substrings/ […]