2501:平衡字符串

时间限制:2 S   /  内存限制:65536 KB
AC:47   /  Submit:118
问题描述

定义平衡字符串$$str$$为:$$str$$中具有相同数量的$$0$$和$$1$$。

例如$$0110,1100$$是平衡字符串,而$$01010,1110$$不是平衡字符串。

一个字符串$$str$$的子串指,可以从$$str$$中连续截取任意个字符形成的字符串。

例如$$abc$$是$$abcde$$的子串,但$$abc$$不是$$abdc$$的子串。

一个字符串$$str$$的子序列指,可以从$$str$$中删除任意个字符形成的字符串。

例如$$abc$$是$$abdc$$的子序列,但$$abc$$不是$$acdb$$的子序列。

若一个串是$$str$$的子串且该串是平衡字符串,那我们称这个串为$$str$$的平衡子串。

若一个串是$$str$$的子序列且该串是平衡字符串,那我们称这个串为$$str$$的平衡子序列。

请你编程求出$$str$$最长平衡子串的长度和最长平衡子序列的长度。

输入描述

第一行是一个正整数$$n$$代表字符串的长度。 ($$1 \leq n \leq 10^5$$)

接下来是一个长度为$$n$$且仅包含字符$$0$$和$$1$$的字符串$$str$$。

输出描述

在一行中输出这个串的最长平衡子串的长度和最长平衡子序列的长度,两者之间用空格隔开,最后换行。

样例输入复制样例

8
01001001

样例输出

4 6

提示说明

最长平衡子串:1001(不唯一,但是最长的)

最长平衡子序列:010101(不唯一,但是最长的)

相关

23-24(2)第2次线上赛


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1