Official

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: