S is string containing only lowercase English alphabets. We need to find if there exists at least one palindromic sub-string whose length is even.
Examples:
Input : aassss
Output : YES
Input : gfg
Output : NO
Approach:
Approach to solve this problem is to check all even-length substrings of the given string and check if any of them is a palindrome. This can be done using nested loops. The outer loop will iterate over all possible starting indices of even-length substrings, while the inner loop will iterate over all possible lengths of such substrings. At each iteration, we can check if the current substring is a palindrome.
- Define a function named “isPalindrome” that takes a string as input and returns a boolean indicating whether the given string is a palindrome or not.
- Define another function named “hasEvenLengthPalindrome” that takes a string as input and returns a boolean indicating whether there exists at least one even-length palindromic substring in the given string or not.
- Traverse the string from the start and fix a starting position “i”.
- Traverse the string from the fixed starting position and fix a length of the substring “len” such that len is even and (i+len) <= n.
- Check if the substring starting from position i and of length len is a palindrome or not by calling the isPalindrome function. If yes, return true.
- If the loop completes successfully, return false.
C++
#include <iostream>#include <string>using namespace std;// function to check if a given string is a palindromebool isPalindrome(string s){ int n = s.length(); for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { return false; } } return true;}// function to check if there exists at least one even-length palindromic substringbool hasEvenLengthPalindrome(string s){ int n = s.length(); for (int i = 0; i < n; i++) { for (int len = 2; i + len <= n; len += 2) { if (isPalindrome(s.substr(i, len))) { return true; } } } return false;}int main(){ string s = "xzyyz"; if (hasEvenLengthPalindrome(s)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
public class Main { // function to check if a given string is a palindrome public static boolean isPalindrome(String s) { int n = s.length(); for (int i = 0; i < n / 2; i++) { if (s.charAt(i) != s.charAt(n - i - 1)) { return false; } } return true; } // function to check if there exists at least one even-length palindromic substring public static boolean hasEvenLengthPalindrome(String s) { int n = s.length(); for (int i = 0; i < n; i++) { for (int len = 2; i + len <= n; len += 2) { if (isPalindrome(s.substring(i, i + len))) { return true; } } } return false; } public static void main(String[] args) { String s = "xzyyz"; if (hasEvenLengthPalindrome(s)) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by shivamgupta0987654321 |
Python
# Function to check if a given string is a palindromedef isPalindrome(s): n = len(s) for i in range(n // 2): if s[i] != s[n - i - 1]: return False return True# Function to check if there exists at least one even-length palindromic substringdef hasEvenLengthPalindrome(s): n = len(s) for i in range(n): for length in range(2, n - i + 1, 2): if isPalindrome(s[i:i + length]): return True return Falseif __name__ == "__main__": s = "xzyyz" if hasEvenLengthPalindrome(s): print("YES") else: print("NO") |
C#
using System;public class GFG{ // function to check if a given string is a palindrome public static bool IsPalindrome(string s) { int n = s.Length; for (int i = 0; i < n / 2; i++) { if (s[i] != s[n - i - 1]) { return false; } } return true; } // function to check if there exists at least one even-length palindromic substring public static bool HasEvenLengthPalindrome(string s) { int n = s.Length; for (int i = 0; i < n; i++) { for (int len = 2; i + len <= n; len += 2) { if (IsPalindrome(s.Substring(i, len))) { return true; } } } return false; } //Driver Code public static void Main() { string s = "xzyyz"; if (HasEvenLengthPalindrome(s)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
// function to check if a given string is a palindromefunction isPalindrome(s) { const n = s.length; for (let i = 0; i < Math.floor(n / 2); i++) { if (s[i] !== s[n - i - 1]) { return false; } } return true;}// function to check if there exists at least one even-length palindromic substringfunction hasEvenLengthPalindrome(s) { const n = s.length; for (let i = 0; i < n; i++) { for (let len = 2; i + len <= n; len += 2) { if (isPalindrome(s.substr(i, len))) { return true; } } } return false;}// Driver codeconst s = "xzyyz";if (hasEvenLengthPalindrome(s)) { console.log("YES");} else { console.log("NO");} |
Output
YES
Time Complexity: O(N^3), where N is the length of the string s. This is because we are using nested loops to generate all possible substrings of even length and then checking if each substring is a palindrome. The isPalindrome function has a time complexity of O(N/2) = O(N) as we are iterating over half of the string.
Space Complexity: O(1) as we are not using any extra data structure to store the substrings.
Notice that a palindrome of even length must contain two same alphabets in the middle. So we just need to check for this condition. If we find two consecutive same alphabets in the string then we output “YES” otherwise “NO”.
Below is the implementation:
C++
// C++ program to check if there is a substring// palindrome of even length.#include <bits/stdc++.h>using namespace std;// function to check if two consecutive same // characters are presentbool check(string s){ for (int i = 0; i < s.length() - 1; i++) if (s[i] == s[i + 1]) return true; return false;}int main(){ string s = "xzyyz"; if (check(s)) cout << "YES" << endl; else cout << "NO" << endl; return 0;} |
Java
// Java program to check if there is a substring // palindrome of even length. class GFG {// function to check if two consecutive same // characters are present static boolean check(String s) { for (int i = 0; i < s.length() - 1; i++) if (s.charAt(i) == s.charAt(i+1)) return true; return false; } // Driver Code public static void main(String[] args) { String s = "xzyyz"; if (check(s)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Python 3 program to check if there is # a substring palindrome of even length.# function to check if two consecutive# same characters are presentdef check(s): for i in range (0, len(s)): if (s[i] == s[i + 1]): return True return False# Driver Codes = "xzyyz"if(check(s)): print("YES")else: print("NO") # This code is contributed# by iAyushRAJ |
C#
// C# program to check if there is a substring // palindrome of even length. using System; public class GFG {// function to check if two consecutive same // characters are present static bool check(String s) { for (int i = 0; i < s.Length - 1; i++) if (s[i] == s[i+1]) return true; return false; } // Driver Code public static void Main() { String s = "xzyyz"; if (check(s)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }} |
Javascript
<script>// Javascript program to check if there is // a substring palindrome of even length. // Function to check if two consecutive same // characters are present function check(s) { for(let i = 0; i < s.length - 1; i++) if (s[i] == s[i + 1]) return true; return false; } // Driver codelet s = "xzyyz"; if (check(s)) document.write("YES");else document.write("NO"); // This code is contributed by suresh07</script> |
PHP
<?php// PHP program to check if there is a // substring palindrome of even length. // function to check if two consecutive // same characters are present function check($s) { for ($i = 0; $i < strlen($s) - 1; $i++) if ($s[$i] == $s[$i + 1]) return true; return false; } // Driver Code$s = "xzyyz"; if (check($s)) echo "YES","\n"; else echo "NO" ,"\n"; // This code is contributed by ajit?> |
Output
YES
Time complexity: O(N) where N is the length of the given string.
Auxiliary space: O(1), as constant extra space is used.
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!
