大厂算法：字符串拼接

一、题目 §

给定 M（0 < M ≤ 30）个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为 N（0 < N ≤ 5）的字符串，

要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，

输入非法或者无法拼接出满足条件的字符串则返回0。

二、输入 §

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

三、输出 §

满足条件的字符串个数

四、示例 §

示例一

输入：
abc 1

输出：
3

• 说明：满足条件的字符串有 a b c 示例二

输入：
dde 2

输出：
2

• 说明：满足条件的字符串有 de 和 ed

五、题解 §

1. 理解题意后就是一个字符串的排列数问题
2. 题目中求排列的字符有重复，这会造成排列结果中出现重复。这通常通过排序和剪枝（保证相同字符在排列结果中前后相对顺序）来解决
3. 题目中还有一个约束是相同字符不能相邻，这和第 2 个约束是不同的。这个相邻体现在排列结果中;上面的体现在解法中，目的是为了结果去重

5.1 Java 实现 §

package org.stone.study.algo.ex202411;

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

/**
 * 字符串拼接
 * 
 * 带约束的排列问题：有相同字符，相同字符不能相邻
 */
public class StringConcatenation {
    private int ans = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        int n = scanner.nextInt();

        int ans = new StringConcatenation().countPermutations(str, n);
        System.out.println(ans);
    }

    public int countPermutations(String str, int n) {
        char[] arr = str.toCharArray();
        int m = arr.length;
        if(m < n) {
            return 0;
        }
        Arrays.sort(arr);
        boolean[] used = new boolean[m];
        Arrays.fill(used, false);
        dfs(arr, -1, 0, used, n);

        return ans;
    }

    /**
     * 回溯求排列，考虑有相同字符，并且
     * @param arr
     * @param pre：递归上一层的字符下标，排列中前一个字符的下标
     * @param count：当前排列中字符个数
     * @param used：访问数组
     * @param n：目标排列字符数
     */
    private void dfs(char[] arr, int pre, int count, boolean[] used, int n) {
        if(count == n) {
            ans++;
            return;
        }

        for(int i = 0; i < arr.length; i++) {
            if(used[i]) {
                continue;
            }
            // 递归父子层次中相同字符不相邻（不同递归深度，控制排列结果中的相邻字符）
            if(pre >= 0 && arr[i] == arr[pre]) {
                continue;
            }
            // 相同字符在递归过程中被选择的顺序，也需要保持前后相对的顺序不变（同一递归深度位置的字符）
            if(i > 0 && arr[i] == arr[i-1] &&!used[i-1]) {
                continue;
            }

            used[i] = true;
            dfs(arr, i, count + 1, used, n);
            used[i] = false;
        }
    }
}

5.2 Python实现 §

def count_permutations(s, n):
    if len(s) < n:
        return 0
    
    arr = sorted(s)
    ans = 0
    used = [False] * len(arr)

    # 回溯求解排列数，pre 表示递归前一个字符的索引，count 表示当前排列的累加字符数
    def backtrack(pre, count):
        nonlocal ans
        if count == n:
            ans += 1
            return
        
        for i in range(len(arr)):
            if used[i]:
                continue

            # 相同字符不能在排列结果中相邻，通过父子递归层级的关系来判断
            if pre >= 0 and arr[i] == arr[pre]:
                continue

            # 相同字符不能在排列结果中同一位置出现，也就是同一递归层级，通过相同字符的前后关系来保证
            if i > 0 and arr[i] == arr[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            backtrack(i, count + 1)
            used[i] = False

        return ans
    
    backtrack(-1, 0)
    return ans


if __name__ == '__main__':
    s1, s2 = input().split()
    n = int(s2)

    print(count_permutations(s1, n))