算法题 15：暗黑的字符串（网易2017年秋招）

来自：网易2017年秋招编程题

题目： 一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。

例如：

• BAACAACCBAAA 连续子串"CBA"中包含了 'A','B','C' 各一个，所以是纯净的字符串

• AABBCCAABB 不存在一个长度为3的连续子串包含 'A','B','C' ,所以是暗黑的字符串

你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串 (1 ≤ n ≤ 30)。

备注：

不定期选出 算法牛人 ，赠与图灵出版社出版赞助的书籍一本。