Número de strings de longitud N sin substring palindrómica

Dados dos enteros positivos N, M . La tarea es encontrar el número de strings de longitud N bajo el conjunto alfabético de tamaño M tal que ninguna substring de tamaño mayor que 1 sea palindrómica.
Ejemplos: 
 

Input : N = 2, M = 3
Output : 6
In this case, set of alphabet are 3, say {A, B, C}
All possible string of length 2, using 3 letters are:
{AA, AB, AC, BA, BB, BC, CA, CB, CC}
Out of these {AA, BB, CC} contain palindromic substring, 
so our answer will be 
8 - 2 = 6.

Input : N = 2, M = 2
Output : 2
Out of {AA, BB, AB, BA}, only {AB, BA} contain 
non-palindromic substrings.

Primero, observe, una string no contiene ninguna substring palindrómica si la string no tiene ninguna substring palindrómica de longitud 2 y 3, porque toda la string palindrómica de las longitudes mayores contiene al menos una substring palindrómica de longitud 2 o 3, básicamente en el centro.
Entonces, lo siguiente es cierto: 
 

• Hay M formas de elegir el primer símbolo de la string.
• Luego hay (M – 1) formas de elegir el segundo símbolo de la string. Básicamente, no debería ser igual al primero.
• Luego hay (M – 2) formas de elegir cualquier símbolo siguiente. Básicamente, no debe coincidir con los símbolos anteriores, que no son iguales.

Sabiendo esto, podemos evaluar la respuesta de las siguientes maneras: 
 

• Si N = 1, entonces la respuesta será M.
• Si N = 2, entonces la respuesta es M*(M – 1).
• Si N >= 3, entonces M * (M – 1) * (M – 2) ^N-2 .

A continuación se muestra la implementación de la idea anterior: 
 

// CPP program to count number of strings of
// size m such that no substring is palindrome.
#include <bits/stdc++.h>
using namespace std;
 
// Return the count of strings with
// no palindromic substring.
int numofstring(int n, int m)
{   
    if (n == 1)
        return m;
 
    if (n == 2)
        return m * (m - 1);
 
    return m * (m - 1) * pow(m - 2, n - 2);
}
 
// Driven Program
int main()
{   
    int n = 2, m = 3;
    cout << numofstring(n, m) << endl;
    return 0;
}

// Java program to count number of strings of
// size m such that no substring is palindrome.
import java.io.*;
 
class GFG {
     
    // Return the count of strings with
    // no palindromic substring.
    static int numofstring(int n, int m)
    {
        if (n == 1)
            return m;
     
        if (n == 2)
            return m * (m - 1);
     
        return m * (m - 1) * (int)Math.pow(m - 2, n - 2);
    }
     
    // Driven Program
    public static void main (String[] args)
    {
        int n = 2, m = 3;
        System.out.println(numofstring(n, m));
    }
}
 
// This code is contributed by ajit.

# Python3 program to count number of strings of
# size m such that no substring is palindrome
 
# Return the count of strings with
# no palindromic substring.
def numofstring(n, m):
    if n == 1:
        return m
 
    if n == 2:
        return m * (m - 1)
 
    return m * (m - 1) * pow(m - 2, n - 2)
 
# Driven Program
n = 2
m = 3
print (numofstring(n, m))
 
# This code is contributed
# by Shreyanshi Arun.

// C# program to count number of strings of
// size m such that no substring is palindrome.
using System;
 
class GFG {
     
    // Return the count of strings with
    // no palindromic substring.
    static int numofstring(int n, int m)
    {
        if (n == 1)
            return m;
     
        if (n == 2)
            return m * (m - 1);
     
        return m * (m - 1) * (int)Math.Pow(m - 2,
                                           n - 2);
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 2, m = 3;
        Console.Write(numofstring(n, m));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to count number
// of strings of size m such
// that no substring is palindrome.
 
// Return the count of strings with
// no palindromic substring.
function numofstring($n, $m)
{
    if ($n == 1)
        return $m;
 
    if ($n == 2)
        return $m * ($m - 1);
 
    return $m * ($m - 1) *
           pow($m - 2, $n - 2);
}
 
// Driver Code
{
    $n = 2; $m = 3;
    echo numofstring($n, $m) ;
    return 0;
}
 
// This code is contributed by nitin mittal.
?>

<script>
// JavaScript program to count number of strings of
// size m such that no substring is palindrome.
 
    // Return the count of strings with
    // no palindromic substring.
    function numofstring(n, m)
    {
        if (n == 1)
            return m;
       
        if (n == 2)
            return m * (m - 1);
       
        return m * (m - 1) * Math.pow(m - 2, n - 2);
    }
 
// Driver Code
 
        let n = 2, m = 3;
        document.write(numofstring(n, m));
 
// This code is contributed by code_hunt.
</script>

Producción 
 

6