[hihoCoder] Beautiful String

描述

We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.)

Here are some example of valid beautiful strings: “abc”, “cde”, “aabbcc”, “aaabbbccc”.

Here are some example of invalid beautiful strings: “abd”, “cba”, “aabbc”, “zab”.

Given a string of alphabets containing only lowercase alphabets (a-z), output “YES” if the string contains a beautiful sub-string, otherwise output “NO”.

输入

The first line contains an integer number between 1 and 10, indicating how many test cases are followed.

For each test case: First line is the number of letters in the string; Second line is the string. String length is less than 10MB.

输出

For each test case, output a single line “YES”/“NO” to tell if the string contains a beautiful sub-string.

提示

Huge input. Slow IO method such as Scanner in Java may get TLE.

样例输入

4
3
abc
4
aaab
6
abccde
3
abb

样例输出

YES
NO
YES
NO

要求是连续递增的字符串,起码有三个,字符数目要相同,就是说遇到abc或者aabbcc就成功了

这个题明显不是给暴搜的,如果枚举string的岂止,复杂度为O(N^3)

首先进行预处理,形如aabbbccdd的字符串处理为[(a, 2), (b, 3), (c, 2), (d, 2)]这种形式
这样有个好处,我们其实要找的就是 chr[i], chr[i + 1], chr[i + 2] 连续递增
cnt[i], cnt[i + 1], cnt[i + 2]相等就行了

但是还有一种情况需要处理,aabbcccccaaaaabbcc, aaabbccc,可以归为一种情况
这个对应的其实就是cnt[i] >= cnt[i + 1] 并且 cnt[i + 1] <= cnt[i + 2]
中间的字母有多少个很关键

AC代码

头文件和细节内容就不贴了

int main() {

    int t, len;
    string s;
    constexpr int maxn = 1e6 + 7;
    cin >> t;
    char chr[maxn];
    int cnt[maxn];
    while (t--) {
        cin >> len >> s;
        int j = 0;
        chr[j] = s[j];
        cnt[j] = 1;
        for (int i = 1; i < len; i++) {
            if (s[i] == s[i - 1]) {
                cnt[j]++;
            }
            else {
                ++j;
                cnt[j] = 1;
                chr[j] = s[i];
            }
        }
        j++;


        bool found = false;
        for (int i = 0; i < j - 2; i++) {
            if ((chr[i] + 1 == chr[i + 1] && chr[i] + 2 == chr[i + 2]) &&
            (cnt[i] >= cnt[i + 1] && cnt[i + 1] <= cnt[i + 2])) {
                found = true;
                break;
            }
        }
        if (found)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}