2501:平衡字符串

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

定义平衡字符串strstr为:strstr中具有相同数量的0011

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

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

例如abcabcabcdeabcde的子串,但abcabc不是abdcabdc的子串。

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

例如abcabcabdcabdc的子序列,但abcabc不是acdbacdb的子序列。

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

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

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

输入描述

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

接下来是一个长度为nn且仅包含字符0011的字符串strstr

输出描述

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

样例输入复制样例

8
01001001

样例输出

4 6

提示说明

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

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

相关

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


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