**Disclaimer**: This is a problem lifted from HackerRank, but their editorial answer wasn't sufficient so I hoped to get better answers. If it's against any policy, please let me know and I'll take this down.

**Problem**: You are given two integers, N and M. Count the number of strings of length N under the alphabet set of size M that doesn't contain any palindromic string of the length greater than 1 as a consecutive substring.

N=2,M=2 -> 2 :: AA, **AB**, **BA**, BB

N=2,M=3 -> 6 :: AA, **AB**, **AC**, **BA**, BB, **BC**, **CA**, **CB**, CC

ABCDE counts as it does not contain any palindromic substrings.

ABCCC does not count as it does contain "CCC", a palindrome of length >1.

**Editorial** Here is the provided answer which I think is wrong:

For N>=3, there are (M−2) ways to choose any next symbol (after the first two) - basically it should not coincide with the previous and pred-previous symbols, that aren't equal.

```
If N=1, return M
If N=2, return M * (M-1)
If N>=3, return M * (M-1) * (M-2)^(N-2)
```

counterexample: N=4, M=3, "ABCC"

**My Solution Try** When I was working on this problem, I tried to find all the strings that contained palindromic substrings and subtracting that from the total, M^N. I ran into a lot of problems with over counting. For example, "ABABA" has "ABA","BAB","ABA" of n=3, and "ABABA" of n=5.

Thanks for any help in elucidating this problem. I really hope for a good answer to figure this out!