Given a string ‘s’ check if all of its palindromic sub-strings are of odd length or not. If yes then print “YES” or “NO” otherwise.
Examples:
Input: str = “neveropen”
Output: NO
Since, “ee” is a palindromic sub-string of even length.Input: str = “madamimadam”
Output: YES
Brute Force Approach: Simply, iterate over each sub-string of ‘s’ and check if it is a palindrome. If it is a palindrome then it must of odd length.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits//stdc++.h> using namespace std; // Function to check if // the string is palindrome bool checkPalindrome(string s) { for (int i = 0; i < s.length(); i++) { if(s[i] != s[s.length() - i - 1]) return false; } return true; } // Function that checks whether // all the palindromic // sub-strings are of odd length. bool CheckOdd(string s) { int n = s.length(); for (int i = 0; i < n; i++) { // Creating each substring string x = ""; for (int j = i; j < n; j++) { x += s[j]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.length() % 2 == 0 && checkPalindrome(x) == true) return false; } } return true; } // Driver code int main() { string s = "neveropen"; if(CheckOdd(s)) cout<<("YES"); else cout<<("NO"); } // This code is contributed by // Sahil_shelangia |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to check if // the string is palindrome static boolean checkPalindrome(String s) { for (int i = 0; i < s.length(); i++) { if(s.charAt(i) != s.charAt(s.length() - i - 1)) return false; } return true; } // Function that checks whether // all the palindromic // sub-strings are of odd length. static boolean CheckOdd(String s) { int n = s.length(); for (int i = 0; i < n; i++) { // Creating each substring String x = ""; for (int j = i; j < n; j++) { x += s.charAt(j); // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.length() % 2 == 0 && checkPalindrome(x) == true) return false; } } return true; } // Driver code public static void main(String args[]) { String s = "neveropen"; if(CheckOdd(s)) System.out.print("YES"); else System.out.print("NO"); } } // This code is contributed // by Arnab Kundu |
Python
# Python implementation of the approach# Function to check if# the string is palindromedef checkPalindrome(s): for i in range(len(s)): if(s[i] != s[len(s)-i-1]): return False return True# Function that checks whether# all the palindromic# sub-strings are of odd length.def CheckOdd(s): n = len(s) for i in range(n): # Creating each substring x = "" for j in range(i, n): x += s[j] # If the sub-string is # of even length and # is a palindrome then, # we return False if(len(x) % 2 == 0 and checkPalindrome(x) == True): return False return True# Driver codes = "neveropen"if(CheckOdd(s)): print("YES")else: print("NO") |
C#
// C# implementation of the approach using System; public class GFG { // Function to check if // the string is palindrome static bool checkPalindrome(String s) { for (int i = 0; i < s.Length; i++) { if(s[i] != s[(s.Length - i - 1)]) return false; } return true; } // Function that checks whether // all the palindromic // sub-strings are of odd length. static bool CheckOdd(String s) { int n = s.Length; for (int i = 0; i < n; i++) { // Creating each substring String x = ""; for (int j = i; j < n; j++) { x += s[j]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.Length % 2 == 0 && checkPalindrome(x) == true) return false; } } return true; } // Driver code public static void Main() { String s = "neveropen"; if(CheckOdd(s)) Console.Write("YES"); else Console.Write("NO"); } } /* This code is contributed by 29AjayKumar*/ |
PHP
<?php // PHP implementation of the approach // Function to check if the string // is palindrome function checkPalindrome($s) { for ($i = 0; $i < strlen($s); $i++) { if($s[$i] != $s[strlen($s) - $i - 1]) return false; } return true; } // Function that checks whether all the // palindromic sub-strings are of odd length. function CheckOdd($s) { $n = strlen($s); for ($i = 0; $i < $n; $i++) { // Creating each substring $x = ""; for ($j = $i; $j < $n; $j++) { $x = $x.$s[$i]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(strlen($x) % 2 == 0 && checkPalindrome($x) == true) return false; } } return true; } // Driver code $s = "neveropen"; if(CheckOdd($s)) echo "YES"; else echo "NO"; // This code is contributed by ita_c ?> |
Javascript
<script>// JavaScript implementation of the approach// Function to check if// the string is palindromefunction checkPalindrome(s){ for (let i = 0; i < s.length; i++) { if(s[i] != s[s.length - i - 1]) return false; } return true;}// Function that checks whether// all the palindromic// sub-strings are of odd length.function CheckOdd(s){ let n = s.length;for (let i = 0; i < n; i++){ // Creating each substring let x = ""; for (let j = i; j < n; j++) { x += s[j]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.length % 2 == 0 && checkPalindrome(x) == true) return false; } } return true;}// Driver codelet s = "neveropen";if(CheckOdd(s)) document.write("YES");else document.write("NO");// This code is contributed by avanitrachhadiya2155</script> |
Output
NO
Time Complexity: O(n3), where n is the length of the given string.
Auxiliary Space: O(n), where n is the length of the given string.
Efficient Approach: To check if all palindromic substrings of s have odd lengths, we can search for an even length palindromic substring of it. We know that every even length palindrome has at least two consecutive characters that are identical (e.g. cxxa, ee). Therefore, we can check two consecutive characters at a time to see if they are the same. If so, then s has an even length palindromic substring and hence output will be NO, and if we find no even length substring the answer will be YES. We can complete this checking after one string traversal.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits//stdc++.h>using namespace std;// Function that checks whether s // contains a even length palindromic// sub-strings or not. bool CheckEven(string s) { for (int i = 1; i < s.size(); ++i) { if (s[i] == s[i - 1]) { return true; } } return false;}// Driver code int main(){ string s = "neveropen"; if(CheckEven(s)==false) cout<<("YES"); else cout<<("NO"); }// This code is contributed by// Aditya Jaiswal |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to check if // the string is palindrome static boolean checkPalindrome(String s){ for (int i = 0; i < s.length(); i++) { if(s.charAt(i) != s.charAt(s.length() - i - 1)) return false; } return true;} // Function that checks whether // all the palindromic // sub-strings are of odd length. static boolean CheckOdd(String s) {int n = s.length();for (int i = 0; i < n; i++){ // Creating each substring String x = ""; for (int j = i; j < n; j++) { x += s.charAt(j); // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.length() % 2 == 0 && checkPalindrome(x) == true) return false; } } return true;}// Driver code public static void main(String args[]){ String s = "neveropen"; if(CheckOdd(s)) System.out.print("YES"); else System.out.print("NO"); }}// This code is contributed// by Arnab Kundu |
Python3
# Python implementation of the approach# Function to check if # the string is palindromedef checkPalindrome(s): for i in range(len(s)): if(s[i] != s[len(s)-i-1]): return False return True# Function that checks whether # all the palindromic # sub-strings are of odd length.def CheckOdd(s): n = len(s) for i in range(n): # Creating each substring x = "" for j in range(i, n): x += s[j] # If the sub-string is # of even length and # is a palindrome then, # we return False if(len(x)% 2 == 0 and checkPalindrome(x) == True): return False return True# Driver codes = "neveropen"if(CheckOdd(s)): print("YES")else: print("NO") |
C#
// C# implementation of the approachusing System; public class GFG {// Function to check if // the string is palindrome static bool checkPalindrome(String s){ for (int i = 0; i < s.Length; i++) { if(s[i] != s[(s.Length - i - 1)]) return false; } return true;} // Function that checks whether // all the palindromic // sub-strings are of odd length. static bool CheckOdd(String s) {int n = s.Length;for (int i = 0; i < n; i++){ // Creating each substring String x = ""; for (int j = i; j < n; j++) { x += s[j]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.Length % 2 == 0 && checkPalindrome(x) == true) return false; } } return true;} // Driver code public static void Main(){ String s = "neveropen"; if(CheckOdd(s)) Console.Write("YES"); else Console.Write("NO"); }} /* This code is contributed by 29AjayKumar*/ |
PHP
<?php // PHP implementation of the approach// Function to check if the string // is palindrome function checkPalindrome($s){ for ($i = 0; $i < strlen($s); $i++) { if($s[$i] != $s[strlen($s) - $i - 1]) return false; } return true;} // Function that checks whether all the // palindromic sub-strings are of odd length. function CheckOdd($s) { $n = strlen($s); for ($i = 0; $i < $n; $i++) { // Creating each substring $x = ""; for ($j = $i; $j < $n; $j++) { $x = $x.$s[$i]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(strlen($x) % 2 == 0 && checkPalindrome($x) == true) return false; } } return true;}// Driver code $s = "neveropen";if(CheckOdd($s)) echo "YES"; else echo "NO"; // This code is contributed by ita_c?> |
Javascript
<script>// Javascript implementation of the approach// Function to check if// the string is palindromefunction checkPalindrome(s){ for (let i = 0; i < s.length; i++) { if(s[i] != s[(s.length - i - 1)]) return false; } return true;}// Function that checks whether// all the palindromic// sub-strings are of odd length.function CheckOdd(s){ let n = s.length;for (let i = 0; i < n; i++){ // Creating each substring let x = ""; for (let j = i; j < n; j++) { x += s[j]; // If the sub-string is // of even length and // is a palindrome then, // we return False if(x.length % 2 == 0 && checkPalindrome(x) == true) return false; } } return true;}// Driver codelet s = "neveropen";if(CheckOdd(s)) document.write("YES");else document.write("NO");// This code is contributed by rag2127</script> |
Output
NO
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!
