Official

C - Dango Editorial by en_translator


For convenience, we assume that - is a level-\(0\) dango string. If the string does not contain level-\(0\) or greater dango string, then the answer to the original problem is \(-1\).

We consider a dango string with rightmost character being - (right dango string) and one with leftmost character being - (left dango string) separately, and then find the larger level (=longest) of them. For now, we only consider right dango string.

A right dango string can be the longest one if it consists of a - and as many preceding zero-or-more os as possible. Let us call it a maximal right dango string.

Example: oo--o-oooo-o has four maximal dango strings: oo-, -, o-, and oooo-. Generally, the number of maximal right dango strings equals the number of -s in the string.

One can find the level of all maximal right dango strings in a total of \(O(N)\) time by scanning the string from the beginning.

Once you implement an algorithm for maximal right dango strings, you can reverse the string and apply the same algorithm to process maximal left dango strings too.
Thus, one can find the levels of all maximal dango strings in a total of \(O(N)\) time; all that left is to find the maximum value among them.

The following is a sample code.

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    string S;
    cin >> S;

    unsigned ans{};

    for (unsigned flip{}; flip < 2; ++flip) {
        // 極大な右ダンゴ文字列のレベルを列挙する
        unsigned level{};
        for (unsigned i{}; i < N; ++i)
            if (S[i] == '-') {
                // '-' に対応する極大な右ダンゴ列のレベルは、直前までの 'o' の個数
                ans = max(ans, level);
                level = 0;
            } else
                ++level;
        // 文字列を反転
        reverse(begin(S), end(S));
    }

    if (ans)
        cout << ans << endl;
    else
        cout << "-1" << endl;

    return 0;
}

posted:
last update: