Compruebe si todas las substrings palindrómicas tienen una longitud impar

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>
Producción

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>
Producción: 

NO

 

Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por indrajit1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *