思路：DFS枚举

这道题的思路其实有点像这道LeetCode题：47. 全排列 II - 力扣（LeetCode）

因为给定的字符串中有重复的字符，因此我们需要对字符串进行排序，然后做一个去重操作

比如给定的字符串是"abba"，要求我们生成长度为2的两个字符，那其实只有两种情况："ab"和"ba"，因此需要去除冗余的"ab"和"ba"，就需要利用到一些去重的技巧，具体可以参考下面代码。

本题在上面这道LeetCode的题目上，增加了两个条件：构成的新字符串的长度为$k$以及新字符串的相邻元素不能相等。

题目描述

给定 $M$ 个字符( a-z ) ，从中取出任意字符(每个字符只能用一次)拼接成长度为 $N$ 的字符串，要求相同的字符不能相邻。

计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回 $0$ 。

输入描述

给定长度为 $M$ 的字符列表和结果字符串的长度 $N$ ，中间使用空格(" ")拼接。

• $0 \lt M \lt 30$
• $0 \lt N \le 5$

输出描述

输出满足条件的字符串个数。

示例1

输入

abc 1

输出

3

说明： 给定的字符为 abc ，结果字符申长度为 $1$ ，可以拼接成 $a、b、c$ ，共 $3$ 种。

示例2

输入

dde 2

输出

2

说明：

给定的字符为 dde ，果字符串长度为 $2$ ，可以拼接成 de、ed， 共 $2$ 种。