题目描述

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

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

思路：DFS枚举

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

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

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

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