思路：DFS枚举

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

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

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

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

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];

rl.on('line', (line) => {
    inputLines.push(line);
});

rl.on('close', () => {
    const [s, k] = inputLines[0].split(' ');
    const sArray = s.split('');
    sArray.sort(); // 将字符串按照字典序排序，方便后续去重操作
    const kInt = parseInt(k);
    let ans = 0;
    const n = sArray.length;
    const vis = Array(n).fill(false); // 用于标记当前字符是否被选取
    const v = []; // 存储对应的字符串序列

    // 定义深度优先搜索函数
    function dfs(u) {
        if (u === kInt) {
            ans += 1;
            return;
        }
        for (let i = 0; i < n; i++) {
            // 如果当前字符已经被使用过，或者与上一个字符一样（但上一个字符未被使用），则跳过
            if (vis[i] || (i > 0 && sArray[i] === sArray[i - 1] && !vis[i - 1])) {
                continue;
            }
            // 如果相邻字符相同，则跳过
            if (v.length && v[v.length - 1] === sArray[i]) {
                continue;
            }
            // 将当前字符添加到序列中，更新标记，并进行递归
            v.push(sArray[i]);
            vis[i] = true;
            dfs(u + 1);
            // 回溯操作，将当前字符弹出序列，还原标记
            v.pop();
            vis[i] = false;
        }
    }

    // 从起始状态开始深度优先搜索
    dfs(0);

    // 输出结果
    console.log(ans);
});

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static char[] s;
    static int k;
    static int ans = 0;
    static int n;
    static boolean[] vis;
    static StringBuilder v = new StringBuilder();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String input = scanner.nextLine();
        String[] inputArray = input.split(" ");
        s = inputArray[0].toCharArray();
        Arrays.sort(s);  // 将字符数组按照字典序排序，方便后续去重操作
        k = Integer.parseInt(inputArray[1]);
        n = s.length;
        vis = new boolean[n];  // 用于标记当前字符是否被选取

        // 调用深度优先搜索函数
        dfs(0);

        // 输出结果
        System.out.println(ans);
    }

    // 定义深度优先搜索函数
    static void dfs(int u) {
        if (u == k) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            // 如果当前字符已经被使用过，或者与上一个字符一样（但上一个字符未被使用），则跳过
            if (vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1])) {
                continue;
            }
            // 如果相邻字符相同，则跳过
            if (v.length() > 0 && v.charAt(v.length() - 1) == s[i]) {
                continue;
            }
            // 将当前字符添加到序列中，更新标记，并进行递归
            v.append(s[i]);
            vis[i] = true;
            dfs(u + 1);
            // 回溯操作，将当前字符从序列中移除，还原标记
            v.deleteCharAt(v.length() - 1);
            vis[i] = false;
        }
    }
}

Python

# 从输入中读取字符串 s 和整数 k
s, k = input().split()
s = list(s)
s.sort()  # 将字符串按照字典序排序，方便后续去重操作
k = int(k)
ans = 0
n = len(s)
vis = [False] * n  # 用于标记当前字符是否被选取
v = []  # 存储对应的字符串序列

# 定义深度优先搜索函数
def dfs(u):
    if u == k:
        nonlocal ans
        ans += 1
        return
    for i in range(n):
        # 如果当前字符已经被使用过，或者与上一个字符一样（但上一个字符未被使用），则跳过
        if vis[i] or (i > 0 and s[i] == s[i - 1] and not vis[i - 1]):
            continue
        # 如果相邻字符相同，则跳过
        if len(v) and v[-1] == s[i]:
            continue
        # 将当前字符添加到序列中，更新标记，并进行递归
        v.append(s[i])
        vis[i] = True
        dfs(u + 1)
        # 回溯操作，将当前字符弹出序列，还原标记
        v.pop()
        vis[i] = False

# 从起始状态开始深度优先搜索
dfs(0)
print(ans)

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

string s;
int k;
int ans = 0;
int n;
vector<bool> vis;
string v;

// 定义深度优先搜索函数
void dfs(int u) {
    if (u == k) {
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        // 如果当前字符已经被使用过，或者与上一个字符一样（但上一个字符未被使用），则跳过
        if (vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1])) {
            continue;
        }
        // 如果相邻字符相同，则跳过
        if (!v.empty() && v.back() == s[i]) {
            continue;
        }
        // 将当前字符添加到序列中，更新标记，并进行递归
        v.push_back(s[i]);
        vis[i] = true;
        dfs(u + 1);
        // 回溯操作，将当前字符弹出序列，还原标记
        v.pop_back();
        vis[i] = false;
    }
}

int main() {
    // 读取输入
    cin >> s >> k;
    sort(s.begin(), s.end());  // 将字符串按照字典序排序，方便后续去重操作
    n = s.length();
    vis = vector<bool>(n, false);  // 用于标记当前字符是否被选取

    // 从起始状态开始深度优先搜索
    dfs(0);

    // 输出结果
    cout << ans << endl;

    return 0;
}

题目描述

给定 $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$ 种。