Official Editorial (C++)

Solution (Two Pointers)

For each query we can keep a sliding window where no more than $m$ letters in the window are not $c$.

Implementation

Time Complexity: $\mathcal{O}(nq)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int garland_len;
	int query_num;
	string garland;
	cin >> garland_len >> garland >> query_num;

	for (int i = 0; i < query_num; i++) {

Copy
import java.io.*;
import java.util.*;

public class Garland {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int garlandLen = Integer.parseInt(br.readLine());
		String garland = br.readLine();
		int queryNum = Integer.parseInt(br.readLine());

Alternative Solution (Two Pointers with Prefix Sums)

For each query we can use prefix sums to check the number of occurrences of a given letter $c$ and use two pointers to find the maximum Koyomity ending at a given pointer $p2$ from $0 \dots n$.

Implementation

Time Complexity: $\mathcal{O}(n(k+q))$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1500;

int dp[26][MAX_N + 1];

int main() {
	int garland_len;
	string garland;

Copy
import java.io.*;
import java.util.*;

public class Garland {
	private final static int MAX_N = 1500;
	public static void main(String[] args) {
		Kattio io = new Kattio();

		int garlandLen = io.nextInt();
		String garland = io.next();

Alternative Solution (Dynamic Programming)

We are performing up to $200\,000$ queries, so it may be optimal to have some way to quickly precompute our answer in constant time.

We can use dynamic programming to cache such answers.

Define $\texttt{dp}[i][j][k]$ to be the best possible score of the first $i$ characters, with $j$ amount painted of character $k$. Either two things can happen when we add an additional character.

1. We append the character and paint an additional square.

   $$\texttt{dp}[i+1][j+1][k] = \max(\texttt{dp}[i+1][j+1][k], \texttt{dp}[i][j][k] + 1)$$

2. We append the character, but since it is the same as our previous character we get to "save" a paint.

   $$\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k] + 1)$$

Since this only gives us the best possible score that ends with length $i$, we can just take the current best and translate it using $\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k])$.

Now, we can query the max painting score for any substring containing the first character. However, this is not required; we only have to query the optimal paintings with size $n$ (the full string) with $\texttt{dp}[n][m_i][c_i]$.

Implementation

Time Complexity: $\mathcal{O}(n^2k + q)$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1500;

int dp[MAX_N + 1][MAX_N + 1][26];
int garland[MAX_N + 1];

int main() {
	int garland_len;