题解

题目类型：双指针 / 线性扫描
核心目标：给定长度为 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;
const long long N=1e6+5;
long long n,s1,s2,h1,h2,wi,ans;
char s[N];
int main(){
	cin>>n>>s+1;
	for(int i=0,l=1,r=n;l<=r;l=max(i+1,l+1)){
        while(s[l]=='j'&&l<=r) l++;
		wi=0;
		if(l<=r){
			for(i=l;i<=r;i++){
			if(s[i]=='j') s1++,h1++;
			else s2++,h2++;
			if(s1>s2) break;
			if(h2>=h1) h1=h2=0,wi=i;
		}
		}
		if(wi) i=wi;
		ans=max((i-l+1)*1ll,ans);
		s1=s2=h1=h2=0;
	}
	cout<<ans<<'\n';
}