企业官网建设流程全解析

4073.统计好字符串数目

难度：困难

问题描述：

给你一个整数n。

如果一个字符串仅由字符'a'和'b'组成，且满足以下条件之一，则该字符串被认为是好的：

它只包含一种字符，且其长度为奇数。

它可以写成s=s1+s2的形式，其中s1和s2是非空的好字符串，且s1的最后一个字符与s2的第一个字符不同。

返回长度为n的好的字符串的数量，模10**9+7。

这里，+表示字符串拼接。

示例1：

输入：n=4

输出：6

解释：

好的字符串有"aaab"、"abbb"、"baaa"、"bbba"、"abab"和"baba"。

例如，"aaab"="aaa"+"b"。这两个部分都是好的，因为每个部分都只包含一种字符且长度为奇数，并且它们在边界处的字符不同。

同样地，"ab"="a"+"b"是好的，所以"abab"="ab"+"ab"也是好的，因为它们的边界字符不同。

因此，答案为6。

示例2：

输入：n=3

输出：4

解释：

好的字符串有"aaa"、"bbb"、"aba"和"bab"。因此，答案为4。

示例3：

输入：n=2

输出：2

解释：

好的字符串有"ab"和"ba"。因此，答案为2。

提示：

1<=n<=10**15

问题分析：

本问题根据n人为构造能够生成的好字符串是比较高效的，这用递归方法实现。

如果n=1，好字符串有两个，分别是’a’，’b’；

如果n=2，好字符串也是两个，分别是’ab’，’ba’；

如果n=3，好字符串也是四个，分别是’aba’，’bab’，’aaa’，’bbb’；

......

如果找到了n-1位的好字符串，那么构造n位好字符串就比较容易了，用’a’和’b’分别去与n-1位的各个好字符串进行组合就可以了。组合规则如下，如果n-1位的好字符串首位为’b’，则可以在前面添加’a’，否则添加’b’；如果n-1位的好字符串最后一位为’b’，则可以在后面添加’a’，否则添加’b’。

函数get_all_array(n)实现了构造所有n位好字符串的功能。

主程序只需要输入整数n，即可生成n位好字符串数组，最后展示所有的好字符串数组，并输出其长度，即为n位好字符串的个数，问题得以解决。

程序如下：

#通过递归生成长度为n的好字符串数组并返回 def get_all_array(n): if n==1: return ['a','b'] elif n==2: return ['ab','ba'] elif n==3: return ['aba','bab','aaa','bbb'] else: d=[] c=get_all_array(n-1) for i in c: d.append('a'+i if i[0]=='b' else 'b'+i) d.append(i+'a' if i[-1]=='b' else i+'b') d=list(set(d)) d.sort() return d #主程序 n=int(input('pls input n=')) t=get_all_array(n) l=len(t) l=l%(10**9+7) print(f'长度为{n}的好字符串有{t}') print(f'长度为{n}的好字符串共有{l}个')

运行实例一

pls input n=1

长度为1的好字符串有['a', 'b']

长度为1的好字符串共有2个

运行实例二

pls input n=3

长度为3的好字符串有['aba', 'bab', 'aaa', 'bbb']

长度为3的好字符串共有4个

运行实例三

pls input n=7

长度为7的好字符串有['aaababa', 'abaaaba', 'ababaaa', 'abababa', 'ababbba', 'abbbaba', 'baaabab', 'babaaab', 'bababab', 'bababbb', 'babbbab', 'bbbabab']

长度为7的好字符串共有12个

运行实例四

pls input n=10

长度为10的好字符串有['aaabababab', 'abaaababab', 'ababaaabab', 'abababaaab', 'ababababab', 'ababababbb', 'abababbbab', 'ababbbabab', 'abbbababab', 'baaabababa', 'babaaababa', 'bababaaaba', 'babababaaa', 'bababababa', 'babababbba', 'bababbbaba', 'babbbababa', 'bbbabababa']

长度为10的好字符串共有18个

发布文章之后，总感觉有些问题，隐隐有些不安，如果真有问题，很多读者在看，这不是闹笑话吗？到晚上的时候，终于发现了这个问题，如果n为奇数时，应该包含有奇数个单字符’a’和’b’，但运行实例三，输入n=7，结果并没有出现7个’a’和’b’，问题找到之后，我赶快将文章阅读权限设置为只有自己可以看，等我修改完善之后再开放阅读权限。

其实出现这个问题，在当时我已经注意到n=3时，包含有’aaa’和’bbb’，但按照递归的规则，单个字符出现在一个好字符串前面或后面必然和这个字符串的第一个字符以及最后一个字符不同，这就导致不可能生成奇数个单字符的情况，所以应该把这种当n为奇数时产生奇数个单字符的情况补上去，才是完善的。

最终程序如下：

#通过递归生成长度为n的好字符串数组并返回 def get_all_array(n): if n==1: return ['a','b'] elif n==2: return ['ab','ba'] elif n==3: return ['aba','bab','aaa','bbb'] else: d=[] c=get_all_array(n-1) for i in c: d.append('a'+i if i[0]=='b' else 'b'+i) d.append(i+'a' if i[-1]=='b' else i+'b') if n%2==1: d.append('a'*n) d.append('b'*n) d=list(set(d)) d.sort() return d #主程序 n=int(input('pls input n=')) t=get_all_array(n) l=len(t) l=l%(10**9+7) print(f'长度为{n}的好字符串有{t}') print(f'长度为{n}的好字符串共有{l}个')

运行实例一

pls input n=5

长度为5的好字符串有['aaaaa', 'aaaba', 'abaaa', 'ababa', 'abbba', 'baaab', 'babab', 'babbb', 'bbbab', 'bbbbb']

长度为5的好字符串共有10个

运行实例二

pls input n=6

长度为6的好字符串有['aaaaab', 'aaabab', 'abaaab', 'ababab', 'ababbb', 'abbbab', 'abbbbb', 'baaaaa', 'baaaba', 'babaaa', 'bababa', 'babbba', 'bbbaba', 'bbbbba']

长度为6的好字符串共有14个

运行实例三

pls input n=7

长度为7的好字符串有['aaaaaaa', 'aaaaaba', 'aaababa', 'abaaaaa', 'abaaaba', 'ababaaa', 'abababa', 'ababbba', 'abbbaba', 'abbbbba', 'baaaaab', 'baaabab', 'babaaab', 'bababab', 'bababbb', 'babbbab', 'babbbbb', 'bbbabab', 'bbbbbab', 'bbbbbbb']

长度为7的好字符串共有20个

运行实例四

pls input n=10

长度为10的好字符串有['aaaaaaaaab', 'aaaaaaabab', 'aaaaababab', 'aaabababab', 'abaaaaaaab', 'abaaaaabab', 'abaaababab', 'ababaaaaab', 'ababaaabab', 'abababaaab', 'ababababab', 'ababababbb', 'abababbbab', 'abababbbbb', 'ababbbabab', 'ababbbbbab', 'ababbbbbbb', 'abbbababab', 'abbbbbabab', 'abbbbbbbab', 'abbbbbbbbb', 'baaaaaaaaa', 'baaaaaaaba', 'baaaaababa', 'baaabababa', 'babaaaaaaa', 'babaaaaaba', 'babaaababa', 'bababaaaaa', 'bababaaaba', 'babababaaa', 'bababababa', 'babababbba', 'bababbbaba', 'bababbbbba', 'babbbababa', 'babbbbbaba', 'babbbbbbba', 'bbbabababa', 'bbbbbababa', 'bbbbbbbaba', 'bbbbbbbbba']

长度为10的好字符串共有42个