问题 F: 小P的秘籍

问题 F: 小P的秘籍

时间限制: 1 Sec  内存限制: 256 MB
提交: 53  解决: 20
[提交] [状态] [讨论版] [命题人:]
题目描述
小P马上就要来到程序设计大赛的现场、上了,他希望能够AK这次比赛,所以他找到了一个字符串。
这个字符串长度为n,由A和K组成。这个字符串被小p称为AK串。小P任意截取一个区间s,使得这个区间从左往右或从右往左在读取子串的过程中,子串中字母K的个数始终不小于A的个数。小p希望知道能够截取区间s的最大长度。
如果小p得到了这个区间的最大长度,那么他就会得到一个AK 这次比赛的秘籍,请你帮助他得到这个区间的最大长度。
输入
第一行一个整数n (n<=106),接下来一个长度为n的只含有A,K的字符串
输出
一个整数,区间的最大长度
样例输入 Copy
6
AKAKKA
样例输出 Copy
4
提示
样例解释
取出区间为KAKK


对于30%数据,N<=2000。

对于另外10%数据,a或者k其中一个仅出现一次。

对于全部数据 N<=10^6。