I think this problem can be easily solved using DP, mostly because of the 1st condition.

Lets denote memo[len][last] as the number of strings with length len and that end in letter last.

Now, we can build the number of strings that end in last according to the parity of len:

- If len is odd, then last must belong to the k valid characters
- If len is even, then last can be any character.

The only condition left is the 1st one, which means that:

memo[len][last] = \sum\limits_{before \in \Sigma, before \neq last} memo[len-1][before]

Where \Sigma is the english alphabet.

But this makes us to make an extra iteration over all before values (therefore, our complexity would be O(n\Sigma^{2})), but this can be avoided by noticing this:

memo[len][last] = (\sum\limits_{before \in \Sigma} memo[len-1][before] ) - memo[len-1][last]

But how does this help? In fact, we can preprocess the sum value at the end of procesing the length len and storing it in the value prevSum, so for the next iteration we’ll have:

memo[len][last] = prevSum - memo[len-1][last]

Finally, our answer would be the number of strings with length n that can end in any character, thus

ans = \sum\limits_{c \in \Sigma} memo[n][c]

Our complexity will be O(n\Sigma).

C++ Code