D - Longest X Editorial by en_translator
This problem can be solved with so-called “sliding window” algorithm.
The sliding window algorithm is an algorithm to search fast for a segment that satisfies given conditions by sliding the right end to expand the segment or the left end to shrink the segment.
Here is a pseudocode of the algorithm.
r=0, ans=0
for l = 0 to |S| - 1
while it is possible to fill S[l,r+1) with 'X'
r = r + 1
ans = max(ans, r - l)
Note that checking the condition in the 3rd line, that is, to check
is it possible to fill S[l, r+1) with ‘X’? \(\cdots(*)\)
should be done fairly fast enough.
For example, you may precompute the cumulative sums of the number of .
, so that \((*)\) can be judged in an \(O(1)\) time.
The total time complexity is \(O(|S|)\).
Sample code in C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
string s;cin>>s;
ll k;cin>>k;
ll n=s.size();
vector<ll>cnt(n+1); // cumulative sums
for(ll i=0;i<=n-1;i++){
if(s[i]=='.')cnt[i+1] = cnt[i] + 1;
else cnt[i+1] = cnt[i];
}// cnt[r] - cnt[l] represents the number of '.' in s[l,r)
ll ans = 0;
ll r = 0;
for(ll l=0;l<=n-1;l++){
while(r<=n-1 && cnt[r+1]-cnt[l] <= k){
r = r+1;
}
ans = max(ans,r-l);
}
cout<<ans<<endl;
return 0;
}
posted:
last update: