Longest Balanced Prefix
National Olympiad — Regional round (2020 season)
Submission name: balans.cpp
Problem summary
Find the longest nonempty prefix of a string over a, b, c, d in which the number of a and b letters together equals the number of c and d letters together. Print 0 if no such prefix exists.
Input
N and a string of N letters.
Output
The length of the longest balanced prefix.
Constraints
1 < N < 1,000,000; letters belong to {a,b,c,d}.
Worked example
An independently prepared example for this explanation.
Input
6 abccdc
Output
4
Solution analysis
- Use a balance: add 1 for a or b, and subtract 1 for c or d. After processing a prefix, this is the difference between the two required counts.
- Whenever the balance becomes zero, save the current prefix length. Processing positions from left to right means the most recently saved length is the largest.
- For abccdc, balances are 1, 2, 1, 0, −1, −2. Only the prefix abcc is balanced, so the answer is 4. The empty prefix is represented by the initial answer 0.
Why it works
After each character, balance is exactly the first group count minus the second group count in that prefix. Thus zero identifies precisely the valid prefixes. Saving every valid length in increasing order leaves the longest one.
Watch out. A balanced substring starting later is irrelevant. Count a and b together, rather than requiring all four letter counts to be equal.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
string letters;
cin >> n >> letters;
int balance = 0;
int answer = 0;
for (int i = 0; i < n; i++) {
if (letters[i] == 'a' || letters[i] == 'b') {
balance++;
} else {
balance--;
}
// Zero balance means this whole prefix has equal group counts.
if (balance == 0) {
answer = i + 1;
}
}
cout << answer << '\n';
}