Check if both halves of a string are Palindrome or not

0 0 4 minutes read

Given a string str, the task is to check whether the given string can be split into two halves, each of which is palindromic. If it is possible, print Yes. Otherwise, print No.

Examples:

Input: str = “naan”
Output: No
Explanation:
Since both halves “na” and “an” are not palindrome.

Input: momdad
Output: Yes
Explanation:
Since both half “mom” and “dad” are palindromes.

Approach:
Follow the steps below to solve the problem:

Iterate over the first ((N / 2) / 2 – 1) indices of the string.
Simultaneously check if both the halves are palindrome or not by the following two conditions:
- If S[i] is not equal to S[N/2 – 1 – i], then first half is not palindromic.
- If S[N/2 + i] is not equal to S[N – 1 – i], then second half is not palindromic.
If none of the above condition is satisfied even once during the iteration, then both halves are palindromic. Print Yes.
Otherwise, print No.

Below is the implementation of the above approach:

C++

// C++ Program to check whether
// both halves of a string is
// Palindrome or not
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if both halves
// of a string are palindrome or not
void checkPalindrome(string S)
{
    // Length of string
    int N = S.size();
 
    // Initialize both part as true
    bool first_half = true;
    bool second_half = true;
 
    int cnt = (N / 2) - 1;
 
    for (int i = 0; i < ((N / 2) / 2); i++) {
 
        // If first half is not palindrome
        if (S[i] != S[cnt]) {
            first_half = false;
            break;
        }
 
        // If second half is not palindrome
        if (S[N / 2 + i] != S[N / 2 + cnt]) {
            second_half = false;
            break;
        }
 
        cnt--;
    }
 
    // If both halves are Palindrome
    if (first_half && second_half) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}
 
int main()
{
    string S = "momdad";
 
    checkPalindrome(S);
 
    return 0;
}

Java

// Java Program to check whether
// both halves of a string is
// Palindrome or not
public class Main {
 
    // Function to check and return if
    // both halves of a string are
    // palindromic or not
    public static void checkPalindrome(
        String S)
    {
        // Length of string
        int N = S.length();
 
        // Initialize both part as true
        boolean first_half = true;
        boolean second_half = true;
 
        int cnt = (N / 2) - 1;
 
        for (int i = 0; i < (N / 2); i++) {
 
            // If first half is not palindrome
            if (S.charAt(i) != S.charAt(cnt)) {
                first_half = false;
                break;
            }
 
            // If second half is not palindrome
            if (S.charAt(N / 2 + i)
                != S.charAt(N / 2 + cnt)) {
                second_half = false;
                break;
            }
 
            cnt--;
        }
 
        // If both halves are Palindrome
        if (first_half && second_half) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        String S = "momdad";
 
        checkPalindrome(S);
    }
}

Python3

# Python3 program to check whether 
# both halves of a string is 
# palindrome or not 
 
# Function to check if both halves 
# of a string are palindrome or not
def checkPalindrome(S):
     
    # Length of string 
    n = len(S)
     
    # Initialize both part as true 
    first_half = True
    second_half = True
     
    cnt = (n // 2) - 1
     
    for i in range(0, int((n / 2) / 2)):
         
        # If first half is not palindrome 
        if (S[i] != S[cnt]):
            first_half = False
            break
             
        # If second half is not palindrome 
        if (S[n // 2 + i] != S[n // 2 + cnt]):
            second_half = False
            break
             
        cnt -= 1
         
    # If both halves are palindrome 
    if (first_half and second_half):
        print('Yes', end = '')
    else:
        print('No', end = '')
 
# Driver code
if __name__=='__main__':
     
    S = 'momdad'
     
    checkPalindrome(S)
                 
# This code is contributed by virusbuddah_

C#

// C# program to check whether 
// both halves of a string is 
// Palindrome or not
using System;
 
class GFG{ 
 
// Function to check and return if 
// both halves of a string are 
// palindromic or not 
public static void checkPalindrome(String S) 
{ 
     
    // Length of string 
    int N = S.Length; 
 
    // Initialize both part as true 
    bool first_half = true; 
    bool second_half = true; 
 
    int cnt = (N / 2) - 1; 
 
    for(int i = 0; i < (N / 2); i++) 
    { 
         
        // If first half is not palindrome 
        if (S[i] != S[cnt]) 
        { 
            first_half = false; 
            break; 
        } 
 
        // If second half is not palindrome 
        if (S[N / 2 + i] != S[N / 2 + cnt])
        { 
            second_half = false; 
            break; 
        } 
        cnt--; 
    } 
 
    // If both halves are Palindrome 
    if (first_half && second_half)
    { 
        Console.Write("Yes"); 
    } 
    else
    { 
        Console.Write("No"); 
    } 
} 
 
// Driver code 
public static void Main() 
{ 
    String S = "momdad"; 
 
    checkPalindrome(S); 
} 
} 
 
// This code is contributed by grand_master

Javascript

<script>
 
// JavaScript Program to check whether
// both halves of a string is
// Palindrome or not
 
 
    // Function to check and return if
    // both halves of a string are
    // palindromic or not
    function checkPalindrome( S) {
     
        // Length of string
        var N = S.length;
 
        // Initialize both part as true
        var first_half = true;
        var second_half = true;
 
        var cnt = parseInt((N / 2)) - 1;
 
        for (i = 0; i < (N / 2); i++) {
 
            // If first half is not palindrome
            if (S.charAt(i) != S.charAt(cnt)) {
                first_half = false;
                break;
            }
 
            // If second half is not palindrome
            if (S.charAt(N / 2 + i) != S.charAt(N / 2 + cnt)) {
                second_half = false;
                break;
            }
 
            cnt--;
        }
 
        // If both halves are Palindrome
        if (first_half && second_half) {
            document.write("Yes");
        } else {
            document.write("No");
        }
    }
 
    // Driver Code
     
 
        var S = "momdad";
 
        checkPalindrome(S);
 
// This code contributed by aashish1995
 
</script>

Output:

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

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!