Dominant Character

传送门

https://codeforces.com/contest/1605

题目简述

给定一个仅由a，b，c组成的字符串，找出这样的最小长度的子串：

• 子串长度至少为2
• 子串中a的个数严格大于b的个数和c的个数

并输出该最小长度。

题目分析

首先我们容易想到，要找出这样的字符串，无非就需要找出两个a之间的b、c的个数是否满足上述条件。因此，需要开数组存储b、c的个数：
b[i]表示字符串中第i号位置及其以前的b的个数总数，c[i]类似。

思路很直接，但是字符串中a的位置可能很多，总不可能任意两个都来验证一遍吧。下面就是关键了：
仔细分析后，可以发现，如果有这样的子串，那么子串内部的a的个数至多为3，至少为2。

以四个a为例来简单证明：
有满足条件的子串，形如 a…a…a…a，约定1、2、3号空位，B为b的个数，C为c的个数，
B_1+B_2+B_3 < 4, C_1+C_2+C_3 < 4 这俩条件必须成立
而B_1>1, C_1>1; B_2>1, C_2>1; B_3>1, C_3>1这三组条件中每组至少有一个成立，显然与上一个条件矛盾了

也就是说，我们只需要验证相邻两个a之间、相隔一个a的两个a之间即可，即可以存储当前a的位序和上一个a、上上个a的位序。

代码实现

#include <iostream>
#include <cstdio>
#include <string>
#define N 1000005
using namespace std;
int b[N], c[N];
char str[N];
int t, n;

int seekString()
{
    // 约定：i为当前a位置，la为上一个a位置，lla为上上个a位置
    int la = 0, lla = 0;
    int res = -1;
    for (int i = 1; i <= n; i++)
    {
        if (str[i] == 'a')
        {
            if (la != 0 && b[i] - b[la] < 2 && c[i] - c[la] < 2 && (res == -1 || res > i - la +1))
            {
                res = i - la + 1;
            }
            if (lla != 0 && b[i] - b[lla] < 3 && c[i] - c[lla] < 3 && (res == -1 || res > i - lla + 1))
            {
                res = i - lla + 1; 
            }
            // 位置更新
            lla = la;
            la = i;
        }
    }
    return res;
}

int main()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> n;
        scanf("%s", str + 1);
        for (int j = 1; j <= n; j++)
        {
            b[j] = b[j - 1] + (str[j] == 'b');
            c[j] = c[j - 1] + (str[j] == 'c');
        }
        cout << seekString() << endl;
    }
}