Check if a string can be split into even length palindromic substrings

0 0 4 minutes read

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 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>

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 zambiatek!