题解

题目类型：双指针 / 线性扫描
核心目标：给定长度为 n 的字符串 s，把字符分成两类——'j' 与 非'j'。在所有子串中，求满足 [ #(\text{非}~'j') \ \ge\ #('j') ] 的最大长度。

直观理解：把每个 'j' 视为 +1，把每个“非 'j'”视为 -1。题目要找的是权值和 ≤ 0 的最长子串。

一、思路概述

• 我们按 左端点 l 从左到右 枚举（但会跳跃推进），对每个 l 尝试尽可能向右扩展右端点 i。
• 在扩展的过程中维护两组计数：
  • s1 / s2：从当前 l 开始到当前位置的全局计数（s1 统计 'j' 数量，s2 统计非 'j' 的数量）。
  • h1 / h2：从上一次被“清零点”之后到当前位置的局部计数。
• 当全局计数出现 s1 > s2（即子串权值和 > 0）时，说明再扩大只会更差，立刻停止本次扩展。
• 当局部计数满足 h2 >= h1 时，说明从“清零点”到当前位置的这段已经**“不亏”（非 'j' 数量不小于 'j'），于是把“清零点”更新到当前位置（h1 = h2 = 0），并记录一个可作为结尾的最优位置** wi = i。

最后本轮确定的最优右端点为：

• 若有记录到 wi，就用 wi；
• 否则用因为 s1 > s2 而停下来的当前位置 i（此时 i 恰好是第一个使得不满足的点，最佳结尾在 i-1，但代码里通过 wi 的维护实现了等价选择）。

记录本轮答案 ans = max(ans, i - l + 1)，并把下一轮的 l 跳到 max(i+1, l+1)，继续做下一次扩展。

另外一个小优化：若 s[l] == 'j'，直接把 l 往右推到**第一个非 'j'**的位置再开始，这能规避明显不优的起点。

二、与代码的对应关系

for (int i=0, l=1, r=n; l<=r; l=max(i+1, l+1)) {
    while (s[l]=='j' && l<=r) l++;     // 1) 起点规避：跳过起始为 'j' 的位置
    wi = 0;
    if (l <= r) {
        for (i=l; i<=r; i++) {         // 2) 右端点从 l 开始扩展
            if (s[i]=='j') s1++, h1++;
            else            s2++, h2++;

            if (s1 > s2) break;        // 3) 全局超过：停止扩展（子串和>0）

            if (h2 >= h1) {            // 4) 局部不亏：重置局部计数并记录“最佳结尾”
                h1 = h2 = 0;
                wi = i;
            }
        }
    }
    if (wi) i = wi;                    // 5) 若有最佳结尾，用它作为本轮右端点
    ans = max(ans, 1LL*(i - l + 1));   // 6) 更新答案（最长长度）
    s1 = s2 = h1 = h2 = 0;             // 7) 清空计数，准备下一轮
}

• s1/s2：当前以 l 为起点的全局计数；
• h1/h2：自上次“清零点”后的局部计数，用来贪心地更新“可作为结尾的最右位置 wi”；
• wi：这次扩展得到的“最优右端点”（保证当前子串满足 #非'j' ≥ #'j'）；
• ans：全局最大长度。

三、正确性解释（为什么可行）

把 'j' 看作 +1，非 'j' 看作 -1。我们要最长的区间和 ≤ 0 的子串。

• 若在某个扩展点出现 s1 > s2（区间和 > 0），再继续扩展只会让子串更大、和更难 ≤ 0，因此立即停止。
• 只要某一段的局部和 ≤ 0（即 h2 >= h1），就可以把“清零点”移动到该处，把这段“吃掉”。这保证了我们总能把“坏的正贡献”砍掉，保留“最不亏”的结尾，使从 l 到当前 i 的整体更容易满足 ≤ 0。
  于是 wi 始终指向最右的、可作为合法结尾的位置。

每轮结束后，从 l 到 i 获得了当前起点下的最优合法区间，于是把下一个 l 跳到 i+1，避免重复工作。

四、边界与细节

• 输入为 cin >> n >> s+1：字符串从下标 1 开始存放，方便与循环匹配。
• 若整个字符串没有任何非 'j'，答案自然为 0。
• 多次清零不会漏解：wi 总能保留“最右合法结尾”，与“首次越界即止”的策略配合可覆盖全部情况。

五、复杂度

• 每个位置作为 l 最多被访问常数次，i 单调不回退，整体为 线性复杂度 O(n)。
• 空间复杂度 O(1)（除输入字符串外）。

六、代码（与题给一致）

#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(res x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline int _max(res x,res y){
    return x>y?x:y;
}
inline int _min(res x,res y){
    return x>y?y:x;
}
const int N=1e6+10;
int n,sum[N],minx;
int head[N],nxt[N],to[N];
char str[N];
int main(){
	memset(head,-1,sizeof(head));
	n=read();
	scanf("%s",str+1);
	for(res i=1;i<=n;i++){
		sum[i]=sum[i-1]+(str[i]=='p'?1:-1);
		minx=_min(minx,sum[i]);
	}
	for(res i=n;i>=0;i--){
		res x=sum[i]-minx;
        nxt[i]=head[x],head[x]=i,to[i]=i;
	}
	res ans=0;
    for(res i=n,pre=n;i>=1;i--){
        if(str[i]=='j')pre=i-1;
        else {
            if(nxt[i-1]>=0&&sum[to[nxt[i-1]]]>=sum[pre])pre=to[nxt[i-1]];
            to[i-1]=pre;
            res pos=pre-i+1;
            ans=max(pos,ans);
        }
    }
    write(ans);
    return 0;
}