Step 1

First, let’s consider an example where eight voters are voting for candidates A, A, B, A, B, B, B, B. Here, how many different sequences of preliminary results can there be?

• If voter \(1\) is the first to be counted: The voting order is [A]ABABBBB, so the sequence of preliminary results is AAAAACBB
• If voter \(1\) is the second to be counted: The voting order is A[A]BABBBB, so the sequence of preliminary results is AAAAACBB
• If voter \(1\) is the third to be counted: The voting order is AB[A]ABBBB, so the sequence of preliminary results is ACAAACBB
• If voter \(1\) is the fourth to be counted: The voting order is ABA[A]BBBB, so the sequence of preliminary results is ACAAACBB
• If voter \(1\) is the fifth to be counted: The voting order is ABAB[A]BBB, so the sequence of preliminary results is ACACACBB
• If voter \(1\) is the sixth to be counted: The voting order is ABABB[A]BB, so the sequence of preliminary results is ACACBCBB
• If voter \(1\) is the seventh to be counted: The voting order is ABABBB[A]B, so the sequence of preliminary results is ACACBBBB
• If voter \(1\) is the eighth to be counted: The voting order is ABABBBB[A], so the sequence of preliminary results is ACACBBBB

Therefore, there are five different sequences of results. However, we can solve this more simply by focusing on the changes in the sequence of results.

---

First, closely observing the preliminary sequences of results reveals the following, where voter \(1\) is the \(i\)-th to be counted:

• 1st character: Always A
• 2nd character: A if \(i \leq 2\), C if \(i > 2\)
• 3rd character: Always A
• 4th character: A if \(i \leq 4\), C if \(i > 4\)
• 5th character: A if \(i \leq 5\), B if \(i > 5\)
• 6th character: C if \(i \leq 6\), B if \(i > 6\)
• 7th character: Always B
• 8th character: Always B

It turns out that the characters change right after \(i = 2, 4, 5, 6\), which means there are \(4 + 1 = 5\) different sequences of results (note that the character at the same position does not change more than twice). But how do we determine the moments when the characters change?

---

If voter \(1\) votes first, the difference in the number of votes between candidates A and B transitions as \(+1 \to +2 \to +1 \to +2 \to +1 \to 0 \to -1 \to -2\). Therefore, each time the order of voter \(1\)’s counting changes, the difference in the number of votes at each stage transitions as follows.

• Up to the first vote:
  • If \(i \leq 1\), voter \(1\)’s vote is counted as the first vote
  • If \(i > 1\), voter \(2\)’s vote is counted as the first vote
  • Meaning, right before and after \(i = 1\), voter \(1\) disappears and voter \(2\) is added
  • Since voters \(1, 2\) vote for A, A, the difference in votes is always \(+1\)
• Up to the second vote:
  • If \(i \leq 2\), voters \(1, 2\)’s votes are counted as the first two votes
  • If \(i > 2\), voters \(2, 3\)’s votes are counted as the first two votes
  • Meaning, right before and after \(i = 2\), voter \(1\) disappears and voter \(3\) is added
  • Since voters \(1, 3\) vote for A, B, the difference in votes is \(+2\) if \(i \leq 2\), \(+0\) if \(i > 2\)
• Up to the fourth vote:
  • If \(i \leq 4\), voters \(1, 2, 3, 4\)’s votes are counted as the first four votes
  • If \(i > 4\), voters \(2, 3, 4, 5\)’s votes are counted as the first four votes
  • Meaning, right before and after \(i = 4\), voter \(1\) disappears and voter \(5\) is added
  • Since voters \(1, 5\) vote for A, B, the difference in votes is \(+2\) if \(i \leq 4\), \(+0\) if \(i > 4\)
• The same applies to other stages

By thinking this way, we can see how the difference in the number of votes at each stage changes with a computational complexity of \(O(N)\). Also, since the voting result is A when the difference is positive, B when negative, and C when zero, we can also determine the moments when the character changes with a computational complexity of \(O(N)\).

---

Step 2

Now, let’s generalize what we’ve discussed so far. Let \(S_k\) be the difference in the number of votes for candidates A and B from voter \(1\) to voter \(k\). Then, when the order \(i\) of voter \(1\)’s counting changes, the difference in the number of votes when the first \(t\) votes are counted changes by the following.

• If voters \(1, t+1\) vote for A, A: Always \(S_t\)
• If voters \(1, t+1\) vote for A, B: \(S_t\) if \(i \leq t\), \(S_t - 2\) if \(i > t\)
• If voters \(1, t+1\) vote for B, A: \(S_t\) if \(i \leq t\), \(S_t + 2\) if \(i > t\)
• If voters \(1, t+1\) vote for B, B: Always \(S_t\)

Therefore, since the voting result is A when the difference is positive, B when negative, and C when zero, we can write the following program to get the answer with a computational complexity of \(O(N)\).

---

Sample Implementation (C++)

#include <iostream>
using namespace std;

int N;
int S[1000009];
char C[1000009];

// Function that returns A if positive, B if negative, and C if zero
char GetSign(int x) {
	if (x > 0) return 'A';
	if (x < 0) return 'B';
	return 'C';
}

int main() {
	// Step 1. Input
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
	}

	// Step 2. Calculate S[i]
	S[0] = 0;
	for (int i = 1; i <= N; i++) {
		if (C[i] == 'A') S[i] = S[i - 1] + 1;
		if (C[i] == 'B') S[i] = S[i - 1] - 1;
	}

	// Step 3. Calculate how many times the character changes
	int TimingChange = 0;
	for (int t = 1; t <= N - 1; t++) {
		int before = S[t]; // Difference in votes when i <= t
		int after = S[t];  // Difference in votes when i >  t
		if (C[1] == 'A' && C[t + 1] == 'A') after += 0;
		if (C[1] == 'A' && C[t + 1] == 'B') after -= 2;
		if (C[1] == 'B' && C[t + 1] == 'A') after += 2;
		if (C[1] == 'B' && C[t + 1] == 'B') after += 0;

		// Convert the difference in votes to a character
		char sign_before = GetSign(before);
		char sign_after  = GetSign(after);

		// If the character changes, add 1 to TimingChange
		if (sign_before != sign_after) {
			TimingChange += 1;
		}
	}

	// Step 4. Output
	cout << TimingChange + 1 << endl;
	return 0;
}

Sample Implementation (Python)

# Function that returns A if positive, B if negative, and C if zero
def GetSign(x):
    if x > 0:
        return 'A'
    if x < 0:
        return 'B'
    return 'C'

# Step 1. Input
N = int(input())
C = input()

# Step 2. Calculate S[i]
S = [0] * (N + 1)
for i in range(N):
    if C[i] == 'A': S[i + 1] = S[i] + 1
    if C[i] == 'B': S[i + 1] = S[i] - 1

# Step 3. Calculate how many times the character changes
TimingChange = 0
for t in range(1, N):
    before = S[t] # Difference in votes when i <= t
    after  = S[t] # Difference in votes when i >  t
    if C[0] == 'A' and C[t] == 'A': after += 0
    if C[0] == 'A' and C[t] == 'B': after -= 2
    if C[0] == 'B' and C[t] == 'A': after += 2
    if C[0] == 'B' and C[t] == 'B': after += 0

    # Convert the difference in votes to a character
    sign_before = GetSign(before)
    sign_after  = GetSign(after)

    # If the character changes, add 1 to TimingChange
    if sign_before != sign_after:
        TimingChange += 1

# Step 4. Output
print(TimingChange + 1)