Longest Run of Window Minima
National Olympiad — Regional round
Submission name: long.cpp
Problem summary
For every length-k contiguous substring of S, from left to right, take its smallest ASCII character. These characters form a new string. Find the longest contiguous run of equal characters in that new string.
Input
k, then the string S.
Output
The longest equal-character run length (0 if there are no length-k windows).
Constraints
1 ≤ k < 100; |S| < 20,000,000; characters have ASCII codes 33…126.
Worked example
An independently prepared example for this explanation.
Input
3 bcabaa
Output
4
Solution analysis
- Maintain a deque of candidate minimum characters, with increasing indices and strictly increasing character values.
- Discard expired indices and larger/equal characters dominated by the arriving character.
- After each complete window, its minimum is the deque front. Update the current equal-character run and the maximum. The derived string need not be stored.
Why it works
A removed candidate can never become a future minimum before the smaller, later character that dominates it expires. Therefore the deque front is always the current window minimum, and the run counter scans exactly the derived sequence.
Watch out. Compare ASCII codes rather than alphabetic order. Overlapping windows count separately.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A removed candidate can never become a future minimum before the smaller, later character
// that dominates it expires. Therefore the deque front is always the current window minimum, and the
// run counter scans exactly the derived sequence.
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s;
cin>>k>>s;
deque<int>q;
int best=0,run=0,last=-1;
for(int i=0;i<(int)s.size();i++){
while(!q.empty()&&q.front()<=i-k){
q.pop_front();
}
while(!q.empty()&&s[q.back()]>=s[i]){
q.pop_back();
}
q.push_back(i);
if(i+1>=k){
int v=(unsigned char)s[q.front()];
run=(v==last?run+1:1);
last=v;
best=max(best,run);
}
}
cout<<best<<'\n';
}