#P3521. [Poi2014]Salad Bar

    ID: 2731 传统题 1000ms 128MiB 尝试: 560 已通过: 187 难度: 6 上传者: 标签>CF2100提高一维前缀和单调栈最近更大/更小元素二分查找ByDzy

[Poi2014]Salad Bar

题目描述

有一个长度为 nn 的字符串,每一位只会是 p 或 j。你需要取出一个子串 SS(从左到右或从右到左一个一个取出),使得不管是从左往右还是从右往左取,都保证每时每刻已取出的 p 的个数不小于 j 的个数。你需要最大化 ∣S∣|S|。

输入格式

第一行一个数 nn,第二行一个长度 nn 的字符串。

输出格式

SS 的最大长度。

6
jpjppj
4

样例解释

取 pjpp 这个串。

数据范围

n≤106n \le 10^6

题目来源

By Dzy