If we can try all initial position of contiguous o in \(T\), then we can obtain the correct answer. (However, it is impossible to check all possible \(NM\) initial positions.)

We will show the following lemma.

There is an optimal solution where the longest contiguous o starts from the \(N\)-th or prior character of \(T\).

Assume that an optimal solution has the longest contiguous o starting from the \((N+1)\)-th or later character. Then, for each modification of \(i\)-th character, we decide to modify the \((i-N)\)-th character instead (if it exists).
Then, now we have an optimal solution where the longest contiguous o starts \(N\) characters prior than before. Repeating this proves the lemma.

Now the problem has been boiled down as follows.

Solve the problem for all \(i=1,2,\dots,N\).
We want to have as many contiguous o as possible starting from the \(i\)-th character of \(T\). Find the maximum length.

This problem can be solved as follows.

• Do binary search over the furthest end.
  • The conditional branch in the binary search can be determined by checking if the number of x between the initial and last characters is \(K\) or less.

In the binary search, we need to answer the following question: “how many x are there in the first \(i\) characters of \(T\)?” This can be answer in an \(O(1)\) time using the periodicity of \(T\) and a cumulative sum. For more details, see the sample code.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

long long f(long long x,long long n,vector<long long> &rw){
  long long res=(x/n)*rw[n];
  long long rem=x%n;
  res+=rw[rem];
  return res;
}

int main(){
  long long n,m,k;
  string s;
  cin >> n >> m >> k >> s;
  
  vector<long long> rw(n+1,0);
  for(long long i=0;i<n;i++){
    rw[i+1]=rw[i];
    if(s[i]=='x'){rw[i+1]++;}
  }

  long long res=0;
  for(long long i=1;i<=n;i++){
    long long fbeg=f(i-1,n,rw);
    long long l=i,r=n*m;
    while(l<=r){
      long long te=(l+r)/2;
      if(f(te,n,rw)-fbeg<=k){l=te+1;}
      else{r=te-1;}
    }
    res=max(r-i+1,res);
  }
  cout << res << "\n";
  return 0;
}