Número de posiciones en las que se puede insertar una letra de modo que una string se convierta en palíndromo

Dada una string str , necesitamos encontrar el no. de posiciones donde se puede insertar una letra (minúscula) para que la string se convierta en un palíndromo. 

Ejemplos: 

Input : str = "abca"
Output : possible palindromic strings: 
         1) acbca (at position 2)
         2) abcba (at position 4)
         Hence, the output is 2.

Input : str = "aaa"
Output : possible palindromic strings:
         1) aaaa
         2) aaaa
         3) aaaa
         4) aaaa
         Hence, the output is 4. 

Enfoque ingenuo: este enfoque consiste en insertar los 26 alfabetos en cada posición posible, es decir, N+1 posiciones y verificar en cada posición si esta inserción lo convierte en un palíndromo y aumenta el conteo.

Enfoque eficiente:  primero debe observar que debemos realizar la inserción solo en el punto en el que el carácter en ese punto viola la condición del palíndromo, es decir,  . Ahora, habrá dos casos basados ​​en el hecho anterior: 

Caso I: ¿Qué pasa si la string dada ya es un palíndromo? 

Entonces solo podemos insertar en la posición tal que la inserción no viole el palíndromo. 

1. Si la longitud es par, siempre podemos insertar cualquier letra en el medio. 
2. Si la longitud es impar, podemos insertar la letra que está en el medio, a la izquierda o a la derecha. 
3. En ambos casos, podemos insertar la letra que está en el medio (que sea ‘CH’ ), en posiciones iguales a: 
   (número de CH consecutivos a la izquierda de la letra del medio)*2 . 

Caso II: Si no es un palíndromo 

Como se mencionó anteriormente, debemos comenzar a insertar en la posición donde  , por lo que aumentamos el conteo y verificamos los casos si la inserción en cualquier otra posición lo convierte en un palíndromo. 

1. Si  es un palíndromo, entonces podemos insertar * en cualquier posición antes  hasta  que , K en el rango  .(*letra = S[Ni-1]) 
2. Si  es un palíndromo, entonces podemos insertar* en cualquier posición después  de K  en el rango  .(*letra = S[i]) 

En todos los casos seguimos aumentando la cuenta.

Implementación:

// CPP code to find the no.of positions where a
// letter can be inserted to make it a palindrome
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the string is palindrome
bool isPalindrome(string &s, int i, int j)
{
    int p = j;
    for (int k = i; k <= p; k++) {
        if (s[k] != s[p])
            return false;
        p--;
    }
    return true;
}
 
int countWays(string &s)
{
    // to know the length of string
    int n = s.length();
    int count = 0;
 
    // if the given string is a palindrome(Case-I)
    if (isPalindrome(s, 0, n - 1))
    {
        // Sub-case-III)
        for (int i = n / 2; i < n; i++)
        {
            if (s[i] == s[i + 1])
                count++;
            else
                break;
        }
        if (n % 2 == 0) // if the length is even
        {
            count++;
            count = 2 * count + 1; // sub-case-I
        } else
            count = 2 * count + 2; // sub-case-II
    } else {
        for (int i = 0; i < n / 2; i++) {
 
            // insertion point
            if (s[i] != s[n - 1 - i])
            {
                int j = n - 1 - i;
 
                // Case-I
                if (isPalindrome(s, i, n - 2 - i))
                {
                    for (int k = i - 1; k >= 0; k--) {
                        if (s[k] != s[j])
                            break;
                        count++;
                    }
                    count++;
                }
 
                // Case-II
                if (isPalindrome(s, i + 1, n - 1 - i))
                {
                    for (int k = n - i; k < n; k++) {
                        if (s[k] != s[i])
                            break;
                        count++;
                    }
                    count++;
                }
                break;
            }
        }
    }
     
    return count;
}
 
// Driver code
int main()
{
    string s = "abca";
    cout << countWays(s) << endl;
    return 0;
}

// Java code to find the no.of positions where a
// letter can be inserted to make it a palindrome
 
import java.io.*;
 
class GFG {
     
    // Function to check if the string is palindrome
    static boolean isPalindrome(String s, int i, int j)
    {
        int p = j;
        for (int k = i; k <= p; k++) {
            if (s.charAt(k) != s.charAt(p))
                return false;
            p--;
        }
         
        return true;
    }
 
    static int countWays(String s)
    {
         
        // to know the length of string
        int n = s.length();
        int count = 0;
 
        // if the given string is a palindrome(Case-I)
        if (isPalindrome(s, 0, n - 1)) {
             
            // Sub-case-III)
            for (int i = n / 2; i < n; i++) {
                if (s.charAt(i) == s.charAt(i + 1))
                    count++;
                else
                    break;
            }
             
            if (n % 2 == 0) // if the length is even
            {
                count++;
                count = 2 * count + 1; // sub-case-I
            }
            else
                count = 2 * count + 2; // sub-case-II
        }
        else {
            for (int i = 0; i < n / 2; i++) {
 
                // insertion point
                if (s.charAt(i) != s.charAt(n - 1 - i)) {
                    int j = n - 1 - i;
 
                    // Case-I
                    if (isPalindrome(s, i, n - 2 - i)) {
                        for (int k = i - 1; k >= 0; k--) {
                            if (s.charAt(k) != s.charAt(j))
                                break;
                            count++;
                        }
                        count++;
                    }
 
                    // Case-II
                    if (isPalindrome(s, i + 1, n - 1 - i)) {
                        for (int k = n - i; k < n; k++) {
                            if (s.charAt(k) != s.charAt(i))
                                break;
                            count++;
                        }
                        count++;
                    }
                    break;
                }
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "abca";
        System.out.println(countWays(s));
    }
}
 
// This code is contributed by vt_m.

# Python 3 code to find the no.of positions
# where a letter can be inserted to make it
# a palindrome
 
# Function to check if the string
# is palindrome
def isPalindrome(s, i, j):
 
    p = j
    for k in range(i, p + 1):
        if (s[k] != s[p]):
            return False
        p -= 1
     
    return True
 
def countWays(s):
 
    # to know the length of string
    n = len(s)
    count = 0
 
    # if the given string is a palindrome(Case-I)
    if (isPalindrome(s, 0, n - 1)) :
     
        # Sub-case-III)
        for i in range(n // 2, n):
 
            if (s[i] == s[i + 1]):
                count += 1
            else:
                break
         
        if (n % 2 == 0): # if the length is even
            count += 1
            count = 2 * count + 1 # sub-case-I
        else:
            count = 2 * count + 2 # sub-case-II
    else :
        for i in range(n // 2) :
 
            # insertion point
            if (s[i] != s[n - 1 - i]) :
                j = n - 1 - i
 
                # Case-I
                if (isPalindrome(s, i, n - 2 - i)) :
                    for k in range(i - 1, -1, -1):
                        if (s[k] != s[j]):
                            break
                        count += 1
                     
                    count += 1
 
                # Case-II
                if (isPalindrome(s, i + 1, n - 1 - i)) :
                    for k in range(n - i, n) :
                        if (s[k] != s[i]):
                            break
                        count += 1
                     
                    count += 1
                 
                break
     
    return count
 
# Driver code
if __name__ == "__main__":
     
    s = "abca"
    print(countWays(s))
 
# This code is contributed by ita_c

// C# code to find the no. of positions
// where a letter can be inserted
// to make it a palindrome.
using System;
 
class GFG {
     
    // Function to check if the
    // string is palindrome
    static bool isPalindrome(String s, int i,
                                       int j)
    {
        int p = j;
        for (int k = i; k <= p; k++)
        {
            if (s[k] != s[p])
                return false;
            p--;
        }
         
        return true;
    }
 
    static int countWays(String s)
    {
         
        // to know the length of string
        int n = s.Length;
        int count = 0;
 
        // if the given string is
        // a palindrome(Case-I)
        if (isPalindrome(s, 0, n - 1)) {
             
            // Sub-case-III)
            for (int i = n / 2; i < n; i++) {
                if (s[i] == s[i + 1])
                    count++;
                else
                    break;
            }
             
            // if the length is even
            if (n % 2 == 0)
            {
                count++;
                 
                // sub-case-I
                count = 2 * count + 1;
            }
            else
             
                // sub-case-II
                count = 2 * count + 2;
        }
        else {
            for (int i = 0; i < n / 2; i++) {
 
                // insertion point
                if (s[i] != s[n - 1 - i]) {
                    int j = n - 1 - i;
 
                    // Case-I
                    if (isPalindrome(s, i, n - 2 - i)) {
                        for (int k = i - 1; k >= 0; k--) {
                            if (s[k] != s[j])
                                break;
                            count++;
                        }
                        count++;
                    }
 
                    // Case-II
                    if (isPalindrome(s, i + 1, n - 1 - i)) {
                        for (int k = n - i; k < n; k++) {
                            if (s[k] != s[i])
                                break;
                            count++;
                        }
                        count++;
                    }
                    break;
                }
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        String s = "abca";
        Console.Write(countWays(s));
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP code to find the no. of
// positions where a letter can
// be inserted to make it a palindrome
 
// Function to check if the
// string is palindrome
function isPalindrome($s, $i, $j)
{
    $p = $j;
    for ($k = $i; $k <= $p; $k++)
    {
        if ($s[$k] != $s[$p])
            return false;
        $p--;
    }
    return true;
}
 
function countWays($s)
{
     
    // to know the length of string
    $n = strlen($s);
    $count = 0;
 
    // if the given string is
    // a palindrome(Case-I)
    if (isPalindrome($s, 0, $n - 1))
    {
         
        // Sub-case-III)
        for ($i = $n / 2; $i < $n; $i++)
        {
            if ($s[$i] == $s[$i + 1])
                $count++;
            else
                break;
        }
         
        // if the length is even
        if ($n % 2 == 0)
        {
            $count++;
             
            // sub-case-I
            $count = 2 * $count + 1;
        }
        else
         
            // sub-case-II
            $count = 2 * $count + 2;
    }
    else
    {
        for ($i = 0; $i < $n / 2; $i++)
        {
 
            // insertion point
            if ($s[$i] != $s[$n - 1 - $i])
            {
                $j = $n - 1 - $i;
 
                // Case-I
                if (isPalindrome($s, $i, $n - 2 - $i))
                {
                    for ($k = $i - 1; $k >= 0; $k--)
                    {
                        if ($s[$k] != $s[$j])
                            break;
                        $count++;
                    }
                    $count++;
                }
 
                // Case-II
                if (isPalindrome($s, $i + 1,$n - 1 - $i))
                {
                    for ($k = $n - $i; $k < $n; $k++)
                    {
                        if ($s[$k] != $s[$i])
                            break;
                        $count++;
                    }
                    $count++;
                }
                break;
            }
        }
    }
     
    return $count;
}
 
// Driver code
$s = "abca";
echo countWays($s) ;
 
// This code is contributed by nitin mittal
?>

<script>
// Javascript code to find the no.of positions where a
// letter can be inserted to make it a palindrome   
    function isPalindrome(s,i,j)
    {
        let p = j;
    for (let k = i; k <= p; k++)
    {
        if (s[k] != s[p])
            return false;
        p--;
    }
    return true;
    }
 
// Function to check if the string is palindrome
function countWays(s)
{
 
    // to know the length of string
    let n = s.length;
    let count = 0;
   
    // if the given string is a palindrome(Case-I)
    if (isPalindrome(s, 0, n - 1))
    {
     
        // Sub-case-III)
        for (let i = n / 2; i < n; i++)
        {
            if (s[i] == s[i + 1])
                count++;
            else
                break;
        }
        if (n % 2 == 0) // if the length is even
        {
            count++;
            count = 2 * count + 1; // sub-case-I
        } else
            count = 2 * count + 2; // sub-case-II
    } else {
        for (let i = 0; i < n / 2; i++) {
   
            // insertion point
            if (s[i] != s[n - 1 - i])
            {
                let j = n - 1 - i;
   
                // Case-I
                if (isPalindrome(s, i, n - 2 - i))
                {
                    for (let k = i - 1; k >= 0; k--) {
                        if (s[k] != s[j])
                            break;
                        count++;
                    }
                    count++;
                }
   
                // Case-II
                if (isPalindrome(s, i + 1, n - 1 - i))
                {
                    for (let k = n - i; k < n; k++) {
                        if (s[k] != s[i])
                            break;
                        count++;
                    }
                    count++;
                }
                break;
            }
        }
    }
       
    return count;
}
 
// Driver code
let s = "abca";
document.write( countWays(s));
    
    // This code is contributed by avanitrachhadiya2155
</script>

2

Este artículo es una contribución de Harsha Mogali . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.