解题思路

本题要求统计字符串 L 的所有不同重排中，满足“相同字母不能相邻”的排列数量。

因为 L 长度不超过 12，可以使用 DFS + 记忆化搜索 + 计数数组 来解决。

核心思路：

1. 统计每个大写字母出现次数。

题目内容

在一个创意设计工坊中，设计师希望用不同的大写字母瓷砖拼出独特图案，给定一个只包含大写英文字母的图案字符串 $L$ ，要求你给出对 $L$ 重新排列的所有不相同的图案，但是有以下约束条件：

1. 相同的字母不能相邻

输入描述

• 输入一个长度不超过 $12$ 的字符串 $L$ ，确保都是大写的

输出描述

• 输出满足约束条件的L重新排列的所有不相同的排列数

样例1

输入

"AAB"

输出

1

说明

只有"$ABA$"满足条件

样例2

输入

""

输出

1

说明

空也是符合没有相邻的要求

样例3

输入

"AA"

输出

0

说明

$AA$ 是相邻的，所以没有满足条件的