Dada una string ‘s’, compruebe si todas sus substrings palindrómicas tienen una longitud impar o no. En caso afirmativo, escriba «SÍ» o «NO» de lo contrario.
Ejemplos:
Entrada: str = «geeksforgeeks»
Salida: NO
Dado que «ee» es una substring palindrómica de longitud uniforme.
Entrada: str = “madamimadam”
Salida: SÍ
Enfoque de fuerza bruta:
Simplemente, itere sobre cada substring de ‘s’ y verifique si es un palíndromo. Si es un palíndromo, debe tener una longitud impar.
A continuación se muestra la implementación del enfoque anterior:
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 = "geeksforgeeks"; 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 = "geeksforgeeks"; 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 palindrome def 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 code s = "geeksforgeeks" 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 = "geeksforgeeks"; 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 = "geeksforgeeks"; 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 palindrome function 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 code let s = "geeksforgeeks"; if(CheckOdd(s)) document.write("YES"); else document.write("NO"); // This code is contributed by avanitrachhadiya2155 </script>
NO
Enfoque eficiente: para verificar si todas las substrings palindrómicas de s tienen longitudes impares, podemos buscar una substring palindrómica de longitud par. Sabemos que cada palíndromo de longitud par tiene al menos dos caracteres consecutivos que son idénticos (por ejemplo, cxxa, ee). Por lo tanto, podemos verificar dos caracteres consecutivos a la vez para ver si son iguales. Si es así, entonces s tiene una substring palindrómica de longitud par y, por lo tanto, la salida será NO, y si no encontramos una substring de longitud par, la respuesta será SÍ.
Podemos completar esta verificación después de un recorrido de string.
A continuación se muestra la implementación del enfoque anterior:
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 = "geeksforgeeks"; if(CheckEven(s)==false) cout<<("YES"); else cout<<("NO"); } // This code is contributed by // Aditya Jaiswal
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 = "geeksforgeeks"; 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 palindrome def 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 code s = "geeksforgeeks" 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 = "geeksforgeeks"; 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 = "geeksforgeeks"; 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 palindrome function 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 code let s = "geeksforgeeks"; if(CheckOdd(s)) document.write("YES"); else document.write("NO"); // This code is contributed by rag2127 </script>
NO
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)