There are several approaches to solve this problem.

1. Naively following the definition of extended ABC string
   • Straightforward approach
   • Better approach
   • Ingenious approach
2. Using conditions that extended ABC strings satisfy
   • Method 1
   • Better approach
   • Ingenious approach
3. Using regular expression

We explain each approach.
We introduce sample code in C++ and Python. Approaches coming earlier requires less observation, and requires easier grammar; those coming later require less coding.

1. Naively following the definition of extended ABC string

1-1. Straightforward approach

The definition of being an extended ABC string is that “there exist an extended A string \(S _ A\), extended B string \(S _ B\), and extended C string \(S _ C\), such that the concatenation of \(S _ A,S _ B\), and \(S _ C\) in this order equals \(S\).” Concatenating strings does not decrease their length, so the extended A string used in this condition is of length between \(0\) and \(100\), inclusive (same applies to B and C).

Therefore, you can try all the \(101 ^ 3\) combinations of strings \(S _ A,S _ B,S _ C\) and check if any of them coincide with the given string \(S\) to solve the problem.

The following is sample code.

#include <iostream>
#include <string>

using namespace std;

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

    for (int a = 0; a <= 100; ++a) {
        for (int b = 0; b <= 100; ++b) {
            for (int c = 0; c <= 100; ++c) {
                // Print Yes if S equals the concatenation of a copies of A, b copies of B, and c copies of C
                if (string(a, 'A') + string(b, 'B') + string(c, 'C') == S) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }

    // If nothing matches, print No
    cout << "No" << endl;
    return 0;
}

S = input()

for a in range(0, 101):
    for b in range(0, 101):
        for c in range(0, 101):
            # Print Yes if S equals the concatenation of a copies of A, b copies of B, and c copies of C
            if 'A' * a + 'B' * b + 'C' * c == S:
                print('Yes')
                exit()

# If nothing matches, print No
print('No')

1-2. A better way

Let \(|\cdot|\) denote the length of a string.

Since the concatenated string must have a length of \(|S|\), once candidates for \(S _ A\) and \(S _ B\) are fixed, we can determine that the length of \(S _ C\) equals \(|S|-|S _ A|-|S _ B|\). Since the length must be at least \(0\), we only have to consider \(S _ B\) of length between \(0\) and \(|S|-|S _ A|\). Likewise, the length of \(S _ A\) is constrained to \(|S|\) or fewer.

With this observation, the algorithm runs faster.

The following is sample code.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;
    
    int N = S.size();

    for (int a = 0; a <= N; ++a) {
        for (int b = 0; b <= N - a; ++b) {
            int c = N - a - b;
            if (S == string(a, 'A') + string(b, 'B') + string(c, 'C')) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

S = input()
N = len(S)

for a in range(0, N + 1):
    for b in range(0, N - a + 1):
        c = N - a - b
        if 'A' * a + 'B' * b + 'C' * c == S:
            print('Yes')
            exit()

print('No')

1-3. Ingenious approach

One can fix the length of \(S _ A\) to be something like:

• the number of A occurring in \(S\);
• the number of consecutive As in the beginning of \(S\); or
• the position that A occurs for the last time in \(S\).

Therefore, we can use this property to determine it faster.

The following is sample code

#include <iostream>
#include <string>

using namespace std;

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

    int N = S.size();

    for (int i = 0; i + 1 < N; ++i) {
        if (S[i] == 'B' && S[i + 1] != 'B' && S[i + 1] != 'C') {
            // Right after B must be B or C
            // Otherwise, print No
            cout << "No" << endl;
            return 0;
        } else if (S[i] == 'C' && S[i + 1] != 'C') {
            // Right after C must be C
            // Otherwise, print No
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

S = input()

for c, d in zip(S, S[1:]):
    if c == 'B' and d != 'B' and d != 'C':
        # Right after B must be B or C
        # Otherwise, print No
        print('No')
        exit()
    elif c == 'C' and d != 'C':
        # Right after C must be C
        # Otherwise, print No
        print('No')
        exit()

print('Yes')

2-3. Ingenious approach

The conditions described in 2-2 is further rephrased as follows: for any two consecutive characters, they are the same or the latter comes later than the former in alphabetic order.

This is ultimately equivalent to “the characters comprising the string are sorted in alphabetic order.

We can use this condition to solve the problem.

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

using namespace std;

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

    if (ranges::is_sorted(S)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

S = input()

if ''.join(sorted(S)) == S:
    print('Yes')
else:
    print('No')

3. Using regular expressions

A regular expression that represents extended ABC string is A*B*C*.

If your programming language provides with feature that determine if a string matches with a regular expression, you can use it to solve this problem.

The following is sample code.

#include <iostream>
#include <string>
#include <regex>

using namespace std;

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

    if (regex_match(S, regex("A*B*C*"))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

from re import fullmatch

if fullmatch('A*B*C*', input()):
    print('Yes')
else:
    print('No')