E卷-字符串拼接(200分)

字符串拼接

LYA最近迷上了一款字符串拼接游戏。游戏规则如下:

给定一个由小写字母组成的字符集合,以及一个正整数 。从字符集合中任意取出字符(每个字符只能用一次),拼接成一个长度为 的字符串,要求相邻的字符不能相同。

请帮助LYA计算出,给定的字符集合能拼接出多少种满足条件的字符串。如果输入非法或无法拼接出满足条件的字符串,则输出 。

输入格式

输入为一行,包含一个由小写字母组成的字符串和一个正整数 ,两者之间用一个空格分隔。

• 字符串长度
• 

输出格式

输出一个整数,表示能拼接出的满足条件的字符串个数。

样例输入

abc 1

样例输出

3

样例解释

给定的字符集合为 abc,结果字符串长度为 ,可以拼接出 a、b、c 三种字符串,因此输出 。

样例输入

dde 2

样例输出

2

样例解释

给定的字符集合为 dde,结果字符串长度为 ,可以拼接出 de、ed 两种字符串,因此输出 。

数据范围

• 字符串长度
• 

题解

本题可以用回溯法(DFS)来解决。

我们定义一个布尔数组 vis 来记录每个字符是否被使用过。然后从字符集合的第一个字符开始,尝试将它加入结果字符串。如果当前字符没有被使用过,且与结果字符串的最后一个字符不同,就将它加入结果字符串,并标记为已使用。

接下来,我们继续尝试从剩余的未使用字符中选择下一个字符,直到结果字符串的长度达到 。如果能够成功构造出一个满足条件的字符串,就将答案加一。

在尝试每一步时,我们都需要跳过重复的字符,以避免重复计算。这可以通过对字符集合进行排序,然后在遍历时跳过连续相同的字符来实现。

时间复杂度为 ,其中 为结果字符串的长度, 为字符集合的长度。空间复杂度为 ,用于存储字符集合和访问数组。

参考代码

• Python

from itertools import permutations

def count_strings(chars, n):
    res = 0
    for perm in permutations(chars, n):
        if all(perm[i] != perm[i+1] for i in range(n-1)):
            res += 1
    return res

chars, n = input().split()
n = int(n)
print(count_strings(chars, n))

• Java

import java.util.*;

public class Main {
    static int k;
    static char[] cs;
    static int res;
    static boolean[] vis;
    static StringBuilder sb = new StringBuilder();