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