Largest Letter Imbalance
National Olympiad — National round (2018 season)
Submission name: maxdiff.cpp
Problem summary
A string contains at most two different lowercase Latin letters. A contiguous segment has weight equal to the absolute difference between the two letter counts, treating a missing letter as having count zero. Find the largest segment weight.
Source clarification. The printed length bound is 10 ≤ n, although the first two official examples have lengths 5 and 6. The examples above retain their official lengths and use Latin a for the first example’s repeated letter.
Input
n, followed by a string of n adjacent lowercase letters.
Output
The maximum weight.
Constraints
The PDF states 10 ≤ n ≤ 100000, while its first two samples use n=5 and n=6; the solution also handles these smaller lengths.
Worked example
An independently prepared example for this explanation.
Input
5 aaaaa
Output
5
Solution analysis
- Give the first letter in the string value +1 and the other letter value −1. For any segment, the absolute sum of these values is exactly its weight. This remains true if there is only one letter.
- A segment sum is the difference of two prefix sums. The greatest absolute difference between any two prefixes is their overall maximum minus their overall minimum. Track these extremes while scanning, including the empty prefix with sum zero.
- For xyxyxy, the prefixes alternate between 0 and 1, so the answer is 1. For aaaaa, they run from 0 through 5 and the answer is 5. The third sample has a prefix range of 4.
Why it works
The +1/−1 mapping makes every segment sum equal to one letter count minus the other. Every pair of prefixes determines a contiguous segment in one chronological order or the other, and absolute value removes that order. The largest absolute prefix difference is exactly maximumPrefix−minimumPrefix.
Watch out. Include the initial zero prefix. This is a contiguous segment problem, not merely the imbalance of the entire string.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
string letters;
cin >> n >> letters;
int prefix = 0;
// Include the empty prefix so segments starting at position one are considered.
int minimum = 0;
int maximum = 0;
for (char letter : letters) {
prefix += letter == letters[0] ? 1 : -1;
minimum = min(minimum, prefix);
maximum = max(maximum, prefix);
}
cout << maximum - minimum << '\n';
}