C++ Character Evaluation

Background Story

In the microscopic world of life, geneticists are working to decode the code of life – the DNA sequence. They have discovered that a specific gene expression process requires two key proteins to appear in a specific order to be activated. They refer to these two proteins as “guide protein” (denoted by the uppercase letter ‘G’) and “operating protein” (denoted by the uppercase letter ‘O’).

Research shows that an effective activation signal can only form when the “guide protein” G appears before the “operating protein” O.

Task Description

Now, student Li has received a long gene sequence string that contains various uppercase and lowercase letters. He wants to know if there exists a valid “GO” activation signal in this sequence.

Here, existence means that there is a subsequence “GO”, which does not require ‘G’ and ‘O’ to be adjacent. For a string <span><span>s</span></span>, it indicates a valid activation if <span><span>s[i] = 'G'</span></span>, <span><span>s[j] = 'O'</span></span>, and <span><span>i < j</span></span>.

Of course, there may be multiple valid activations in this sequence. Please write code to help student Li analyze this gene sequence.

Input Format

Input a string <span><span>s</span></span>, representing the gene sequence to be analyzed.

Output Format

• If the string does not contain any valid “GO” activation, output <span><span>Signal not activated</span></span>
• If the string contains only one valid “GO” activation, output <span><span>Activation successful</span></span>
• If the string contains multiple valid “GO” activations, output <span><span>Strong activation!</span></span> (Note: the output text and symbols must match)

Data Range

• For 30% of the data, the string contains only ‘G’ or ‘O’, and the length does not exceed 100.
• For 60% of the data, the string length does not exceed 100.
• For 100% of the data, the string length does not exceed 1000, and contains only English letters.

Sample Input 1

<pre><code>sequenceOG

Sample Output 1

<pre><code>Signal not activated

(Explanation: Although there are G and O, O appears before G, which does not satisfy the condition i < j)

Sample Input 2

<pre><code>axGybiOdef

Sample Output 2

<pre><code>Activation successful

(Explanation: G is in the 2nd position, O is in the 7th position, forming one valid activation)

Sample Input 3

<pre><code>GundamOpGOr

Sample Output 3

<pre><code>Strong activation!

(Explanation: The first G can pair with two Os, and the second G can pair with the second O, forming a total of 3 valid activations)

1. Problem Analysis

• Goal: Count all pairs of characters <span><span>(s[i], s[j])</span></span> that satisfy <span><span>i < j</span></span>, where <span><span>s[i] = 'G'</span></span> and <span><span>s[j] = 'O'</span></span>.

• Key Constraint: The order is mandatory. An ‘O’ can only form a valid “activation signal” if a ‘G’ has appeared before it.

2. Algorithm Idea and Explanation

The optimal way to solve this problem is to traverse the string only once and dynamically calculate the result during the traversal. This method is called **”linear scan” or “single pass scan”**.

We need two variables:

<span><span>(1) count_g</span></span>: an integer to record how many ‘G’s we have encountered so far.

<span><span>(2) count_go</span></span>: a long integer (<span><span>long long</span></span>), used to accumulate the total number of valid “GO” activation signals.

The algorithm steps are as follows:

1. Initialize <span><span>count_g = 0</span></span> and <span><span>count_go = 0</span></span>.

2. Start traversing each character in the input string <span><span>s</span></span> from left to right.

3. For the current character being traversed <span><span>c</span></span>:

• If <span><span>c</span></span> is ‘G’, we have found a new “guide protein”. At this point, we just need to add 1 to the value of <span><span>count_g</span></span>.

• If <span><span>c</span></span> is ‘O’, this is a critical moment! This newly discovered ‘O’ can pair with all the ‘G’s that have appeared before it, forming valid activation signals. Therefore, we will add the current value of <span><span>count_g</span></span> to the total <span><span>count_go</span></span>.

When the entire string has been traversed, the value stored in <span><span>count_go</span></span> is the final answer.

To understand through an example:<span><span>s = "GOGOGO"</span></span>

Character Traversed	<span><span>count_g</span></span> Value	<span><span>count_go</span></span> Value	Explanation
(Start)	0	0	Initialization
G	1	0	Encountered the first ‘G’.
O	1	0 + 1 = 1	Encountered ‘O’, it has 1 ‘G’ before it, total +1.
G	2	1	Encountered the second ‘G’.
O	2	1 + 2 = 3	Encountered ‘O’, it has 2 ‘G’s before it, total +2.
G	3	3	Encountered the third ‘G’.
O	3	3 + 3 = 6	Encountered ‘O’, it has 3 ‘G’s before it, total +3.
(End)	3	6	The final result is 6.

This algorithm is very clever because it utilizes the information of ‘G’s accumulated when encountering ‘O’, perfectly solving the “order” problem.

Reference Solution:

#include<bits/stdc++.h>using namespace std;int main() {    string s;    cin >> s;    // count_g records the number of 'G's encountered    long long count_g = 0;    // count_go records the total number of "GO" subsequences satisfying i < j    long long count_go = 0;     // Traverse the string from start to end    for (char c : s) {        if (c == 'G') {            // If the current character is 'G', increase the count of 'G'            count_g++;        } else if (c == 'O') {            // If the current character is 'O', it can form "GO" with all previous 'G's            // So add the number of existing 'G's to the total            count_go += count_g;        }    }    // Determine and output based on the total number of "GO" subsequences    if (count_go == 0) {        cout << "Signal not activated" << endl;    } else if (count_go == 1) {        cout << "Activation successful" << endl;    } else { // count_go > 1        cout << "Strong activation!" << endl;    }    return 0;}