如果将所有连续的相等字符合并后,得到的字符串是回文,我们称一个字符串为好字符串。例如,“aabba”很好,因为在合并步骤之后它将变成“aba”。
给定一个字符串,您必须找到两个值:
1. 偶数长度的好子串的数量;
2.奇数长度的好子串的数量。
输入
输入的第一行包含长度为 n (1 ≤ n ≤ 105) 的单个字符串。字符串的每个字符都是“a”或“b”。
输出
打印两个空格分隔的整数:偶数长度的好子串的数量和奇数长度的好子串的数量。
示例
输入 #1
bb
输出 #1
1 2
输入 #2
baab
输出 #2
2 4
输入 #3
babb
输出 #3
2 5
输入#4
babaa
输出#4
2 7
注意
在示例 1 中,存在三个好的子字符串(“b”、“b”和“bb”)。其中一个长度为偶数,两个长度为奇数。
在示例 2 中,有 6 个好的子字符串(即“b”、“a”、“a”、“b”、“aa”、“baab”)。其中两个长度为偶数,四个长度为奇数。
在示例 3 中,有七个好的子字符串(即“b”、“a”、“b”、“b”、“bb”、“bab”、“babb”)。其中两个长度为偶数,五个长度为奇数。
定义
字符串 s = s1s2... sn 的子字符串 s[l, r] (1 ≤ l ≤ r ≤ n) 是字符串 slsl + 1... sr。
如果字符串 s = s1s2... sn 等于字符串 snsn - 1... s1,则它是回文。