An impassioned circulation of affection

Solución 1 - Dos punteros

Explicación

Para cada consulta podemos mantener una ventana deslizante donde no más de $m$ letras de la ventana son distintas de $c$ .

Implementación

Complejidad temporal: $\mathcal{O}(nq)$

C++Java


#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++) {
		int max_repaint;
		char color;
		cin >> max_repaint >> color;
 
		int l = 0;
		int r = 0;
		int koyomity = 0;
		while (l < garland_len && r < garland_len) {
			while (r < garland_len) {
				if (garland[r] != color) {
					if (max_repaint == 0) break;
					max_repaint--;
				}
				r++;
			}
			koyomity = max(koyomity, r - l);
			max_repaint += garland[l++] != color;
		}
 
		cout << koyomity << '\n';
	}
}


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());
 
		// Leer todas las consultas de antemano es más rápido por alguna razón
		StringBuilder qb = new StringBuilder();
		for (int i = 0; i < queryNum; i++) { qb.append(br.readLine()).append('\n'); }
		StringTokenizer st = new StringTokenizer(qb.toString());
 
		char[] arr = garland.toCharArray();
		StringBuilder out = new StringBuilder();
		for (int i = 0; i < queryNum; i++) {
			int maxRepaint = Integer.parseInt(st.nextToken());
			char color = st.nextToken().charAt(0);
 
			int l = 0;
			int r = 0;
			int koyomity = 0;
			while (l < garlandLen && r < garlandLen) {
				while (r < garlandLen) {
					if (arr[r] != color) {
						if (maxRepaint == 0) break;
						maxRepaint--;
					}
					r++;
				}
				koyomity = Math.max(koyomity, r - l);
				if (arr[l++] != color) maxRepaint++;
			}
			out.append(koyomity).append('\n');
		}
 
		System.out.print(out.toString());
	}
}

Solución 2 - Dos punteros con sumas de prefijos

Explicación

Para cada consulta podemos usar sumas de prefijos para chequear la cantidad de ocurrencias de una letra dada $c$ y usar dos punteros para hallar la Koyomity máxima que termina en un puntero dado $p2$ de $0 \dots n$ .

Implementación

Complejidad temporal: $\mathcal{O}(n(k+q))$

C++Java


#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;
	cin >> garland_len >> garland;
	for (int i = 1; i <= garland_len; i++) {
		int color = garland[i - 1] - 'a';
		dp[color][i]++;
	}
 
	for (int i = 0; i < 26; i++) {
		for (int j = 1; j <= garland_len; j++) { dp[i][j] = dp[i][j - 1] + dp[i][j]; }
	}
 
	int query_num;
	cin >> query_num;
	for (int i = 0; i < query_num; i++) {
		int max_repaint;
		char color;
		cin >> max_repaint >> color;
		color -= 'a';
 
		int l = 1, r = 1, koyomity = 1;
		while (r <= garland_len) {
			int c_count = dp[color][r] - dp[color][l - 1] + max_repaint;
			if (c_count < r - l + 1) {
				l++;
			} else {
				koyomity = max(koyomity, r - l + 1);
				r++;
			}
		}
		cout << koyomity << endl;
	}
}


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();
		int queryNum = io.nextInt();
 
		int[][] dp = new int[26][MAX_N + 1];
		for (int i = 1; i <= garlandLen; i++) {
			int color = (garland.charAt(i - 1) - 'a');
			dp[color][i]++;
		}
 
		for (int i = 0; i < 26; i++) {
			for (int j = 1; j <= garlandLen; j++) {
				dp[i][j] = dp[i][j - 1] + dp[i][j];
			}
		}
 
		for (int i = 0; i < queryNum; i++) {
			int maxRepaint = io.nextInt();
			int color = (io.next().charAt(0) - 'a');
 
			int l = 1;
			int r = 1;
			int koyomity = 1;
			while (r <= garlandLen) {
				int cCount = dp[color][r] - dp[color][l - 1] + maxRepaint;
				if (cCount < r - l + 1) {
					l++;
				} else {
					koyomity = Math.max(koyomity, r - l + 1);
					r++;
				}
			}
			io.println(koyomity);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Solución 3 - Programación Dinámica

Explicación

Estamos haciendo hasta $200\,000$ consultas, así que puede ser óptimo tener alguna forma de precomputar la respuesta rápidamente en tiempo constante.

Podemos usar programación dinámica para cachear esas respuestas.

Definimos $\texttt{dp}[i][j][k]$ como el mejor puntaje posible de los primeros $i$ caracteres, con $j$ cantidad pintada del carácter $k$ . Al agregar un carácter adicional pueden ocurrir dos cosas.

Agregamos el carácter y pintamos una casilla adicional.
$\texttt{dp}[i+1][j+1][k] = \max(\texttt{dp}[i+1][j+1][k], \texttt{dp}[i][j][k] + 1)$
Agregamos el carácter, pero como es el mismo que el carácter anterior podemos “ahorrar” una pintura.
$\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k] + 1)$

Como esto solo nos da el mejor puntaje posible que termina con longitud $i$ , podemos tomar el mejor actual y trasladarlo usando $\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k])$ .

Ahora podemos consultar el puntaje máximo de pintura para cualquier subcadena que contenga el primer carácter. Sin embargo, esto no es necesario; solo hay que consultar las pinturas óptimas de tamaño $n$ (el string completo) con $\texttt{dp}[n][m_i][c_i]$ .

Implementación

Complejidad temporal: $\mathcal{O}(n^2k + q)$

C++


#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;
	cin >> garland_len;
	for (int i = 0; i < garland_len; i++) {
		char a;
		cin >> a;
		garland[i] = (int)(a - 'a');
	}
 
	// i = longitud del string
	// j = cantidad de pintura
	// k = carácter
	for (int k = 0; k < 26; k++) {  // caracteres en minúscula
		for (int i = 0; i < garland_len; i++) {
			for (int j = 0; j < garland_len; j++) {
				// agregamos un carácter
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + 1);
				// si podemos "ahorrar"
				if (garland[i] == k)
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + 1);
			}
		}
	}
 
	// tomamos el mejor actual y lo trasladamos
	for (int k = 0; k < 26; k++) {
		for (int i = 0; i < garland_len; i++) {
			for (int j = 0; j < garland_len; j++) {
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
			}
		}
	}
 
	int query_num;
	cin >> query_num;
	for (int i = 0; i < query_num; i++) {
		int max_repaint;
		char color;
		cin >> max_repaint >> color;
		color -= 'a';
		cout << dp[garland_len][max_repaint][(int)color] << '\n';
	}
}