ABC299C Dango

题意分析¶

我们定义一个 $L$ 阶的 Dango 字符串为：

由字符 'o' 和 '-' 组成；
总长度为 $L+1$；
除开首尾字符，连续中间 $L$ 个字符必须全部是 'o'；
首尾字符中恰好一个是 '-'，另一个是 'o'。

例如：

✅ ooo- 是 3 阶 Dango（首为 o，尾为 -）
✅ -oooo 是 4 阶 Dango（首为 -，尾为 o）
❌ -ooo- 不合法（首尾都是 -）
❌ oooo 没有 -
❌ -oo-o 不合法（中间不是全 o）

题目要求：在一个长度为 $N$ 的字符串 $S$ 中，找到所有子串中最长的 Dango 字符串的阶数。如果不存在合法的 Dango，输出 -1。

解题思路¶

一、关键条件归纳¶

要构成一个 Dango：

必须存在一段长度 $\geq 2$ 的子串；
且该子串中，除首尾外为一整段连续 o；
且首或尾为 -，另一端为 o；
简化后，Dango 的结构就变成：
- o + 若干 o + -，或
- - + 若干 o + o

即我们只需要找到满足这种结构的子串，统计其中 o 的个数 $L$，更新最大值。

二、转化为统计连续 o 的最大值问题¶

我们可以从左到右扫描整个字符串，维护一个变量 cnt 表示当前连续 o 的数量，额外维护 max_cnt 表示所有合法结构中 o 的最大连续长度：

每次遇到 o，cnt++
每次遇到 -：
若 cnt > 0，说明可以与 - 构成合法 Dango（o...o-）
- 更新 max_cnt = max(max_cnt, cnt)
然后重置 cnt = 0，准备统计下一个段

解释：只要存在一个 - 紧跟在连续 o 后，或者 o 紧跟在 - 后形成的 oo...o，我们就认为它可以构成 Dango。

三、特殊情况处理¶

如果整个字符串中不存在 -，则无论 o 连续多少个，都不能构成 Dango，输出 -1
如果所有字符不是 o，也不可能构成合法的 Dango，输出 -1
若存在合法结构，则答案为 max_cnt

实现步骤¶

遍历字符串 $S$，从左到右：
- 用 cnt 统计连续 o 的个数；
- 用布尔变量 has_dash 记录是否出现过 -；
- 每遇到一个 -：
  - 若 cnt > 0，说明可以构成合法 Dango（尾为 -），更新 max_cnt；
  - 重置 cnt = 0
- 每遇到 o，cnt++
循环结束后：
- 因为尾部可能是 o，而之前某个字符是 -，也可能构成合法 Dango（如 -oooo），因此需要再一次检查并更新 max_cnt
输出结果：
- 如果没有 - 或最大阶数为 0，输出 -1
- 否则输出 max_cnt

示范代码¶

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0, cnt = 0;
    for (int i = 0; i < n;i++) 
    { 
        if (s[i] == 'o') 
        {
            cnt++;
        } 
        else 
        {
            ans = max(ans, cnt);
            cnt = 0; // 重置计数器，进入下一次统计
        }
    }
    ans = max(ans, cnt); // 最后一段连续的 o 在更新一次最大值
    if(ans == n) // 说明全是字符 o
    {
        cout << -1;
        return 0;   
    }
    if (ans > 0) 
    {
        cout << ans ;
    } 
    else // 说明没有字符 o
    {
        cout << -1 ;
    }
    return 0;
}

时间复杂度分析¶

遍历整个字符串一次即可完成统计：时间复杂度为 $O(N)$；
空间复杂度为 $O(1)$，只需要几个变量存状态。

总结¶

本题本质是字符串中模式匹配与计数问题；
合法 Dango 字符串的形式具有规律，可归纳为特定结构；
借助一趟遍历即可记录所有可能 Dango 的最大阶数；
边界处理（如只含 o 或只含 -）需特别注意。

该策略直观清晰，易于实现，也符合语法题场景的考察目标。