AtCoder ABC 053 B - A to Z String (5Q, 灰色, 200 点)

制約が なのがびっくり。素直に連続部分列をすべて調べると TLE してしまう。そのような問題は B 問題で登場するイメージがないので、現代なら などとしそうだ。

• 問題へのリンク

問題概要

文字列 の連続する部分文字列であって、先頭が 'A' で末尾が 'Z' であるものを考える。

そのような連続する部分文字列の長さの最大値を求めよ。そのような部分文字列が存在することは保証される。

制約

• 

考えたこと

文字列 を調べていき、次の 2 つの値が求められれば良い。

---

• left ← 文字 S[i] が 'A' であるような i の最小値
• right ← 文字 S[i] が 'Z' であるような i の最大値

---

これらが求められれば、right - left + 1 の値を答えれば良い。

注意

の連続する部分文字列をすべて調べて、そのうち先頭が 'A'、末尾が 'Z' であるようなものについて、その長さの最大値を求める方針も考えられる。

だが、その場合には計算量が となる。それでは TLE となってしまうので注意。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;

    int left = -1, right = -1;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == 'A') if (left == -1) left = i;
        if (S[i] == 'Z') right = i;
    }
    cout << right - left + 1 << endl;
}