观察:满足“相邻字符大小写必须不同”的串,其大小写分布在下标奇偶上必然固定成两种模式之一: 模式 A:下标偶位为大写、奇位为小写; 模式 B:下标偶位为小写、奇位为大写。 因此一个串是“好”,等价于它完全匹配模式 A 或完全匹配模式 B。
“不错”定义为:至多翻转一个字符的大小写后能变成“好”。
设串与两种模式的“失配数”分别为 misA、misB,则最少需要的翻转次数为 min(misA, misB)。
我们称一个只包含英文字母的字符串为好,当且仅当它的相邻字符大小写必须不同;等价地,对于任意相邻的一对字符(如果存在),恰有一个为大写字母、另一个为小写字母。
我们称一个字符串为不错,当且仅当对它其中一个字符至多进行一次大小写翻转(也可以不操作)后,能够变成一个好的字符串。
现在,给定 n 个字符串,请统计其中好的字符串数量,以及不错的字符串数量。