Alternating String

Explicación

Primero, nótese que un string alternante debe tener longitud par. Como la operación 1 (borrar el $i$ -ésimo carácter) se puede usar a lo sumo una vez, solo usamos la operación 1 si el string tiene longitud impar, para que la longitud resultante sea par.

Si el string original tiene longitud impar, hay que elegir qué carácter borrar. Nótese que, al borrar un carácter, cambia la paridad de cada letra siguiente. Una letra que originalmente estaba en un índice impar pasa a un índice par.

Sea $i$ un índice del string $s$ que se borra. El string resultante es $s'$ . Juntos, el prefijo de índices pares antes de $i$ y el sufijo de índices impares después de $i$ forman los índices pares de $s'$ . De forma análoga, el prefijo de índices impares antes de $i$ y el sufijo de índices pares después de $i$ forman los índices impares de $s'$ .

Para ahorrar memoria, el prefijo y el sufijo se pueden representar sobre la marcha. El “prefijo” y el “sufijo” son listas de 26 enteros (uno por letra) que guardan las frecuencias de un carácter: el prefijo son las frecuencias de un carácter a la izquierda de $i$ y el sufijo las frecuencias de un carácter a la derecha de $i$ .

A medida que recorremos los valores de $i$ de $0$ a $n - 1$ , sumamos uno a la frecuencia del carácter en $i$ en el prefijo, y restamos uno a la frecuencia del carácter en $i$ en el sufijo.

Ahora tenemos un string de longitud par. Ya no se puede aplicar la operación 1, solo la operación 2. Hay que determinar cuántas veces hay que aplicar la operación 2. Podemos averiguarlo cambiando cada carácter par al carácter par más frecuente y cada carácter impar al carácter impar más frecuente.

Por ejemplo, dado el string abcbab, es óptimo convertir la c en una a en lugar de convertir todas las a en c. Además, es mejor no cambiar las b porque ya son todas iguales.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
 
	int res = s.length();
 
	// longitud par o impar del string
	if (n % 2 == 0) {
		array<array<int, 26>, 2> letters{};
 
		// llenamos la suma de sufijos
		for (int i = 0; i < s.length(); i++) { letters[i % 2][s[i] - 'a']++; }
 
		int best[2] = {0, 0};
 
		// hallamos la letra que más aparece en índices pares e impares
		for (int i = 0; i < 26; i++) {
			best[0] = max(best[0], letters[0][i]);
			best[1] = max(best[1], letters[1][i]);
		}
 
		res -= (best[0] + best[1]);
	} else {
		array<array<int, 26>, 2> pref{};
		array<array<int, 26>, 2> suff{};
 
		// llenamos la suma de sufijos
		for (int i = n - 1; i > -1; i--) { suff[i % 2][s[i] - 'a']++; }
 
		// probamos índices a borrar
		for (int i = 0; i < n; i++) {
			// el carácter ya no está en el sufijo
			suff[i % 2][s[i] - 'a']--;
 
			int best[2] = {0, 0};
 
			// hallamos la letra que más aparece en índices pares e impares
			for (int j = 0; j < 26; j++) {
				best[0] = max(best[0], suff[1][j] + pref[0][j]);
				best[1] = max(best[1], suff[0][j] + pref[1][j]);
			}
 
			res = min(res, (int)s.length() - best[0] - best[1]);
 
			// el carácter ahora está en el prefijo
			// hay que agregarlo al final del bucle porque
			// si no se contaría cuando está "borrado"
			pref[i % 2][s[i] - 'a']++;
		}
	}
 
	cout << res << '\n';
}
 
int main() {
	int t;
	cin >> t;
 
	while (t--) { solve(); }
}


import java.io.*;
 
public class AlternatingString {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
		int t = Integer.parseInt(br.readLine());
 
		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			String s = br.readLine();
 
			out.println(solve(n, s));
		}
 
		out.flush();
	}
 
	public static int solve(int n, String s) {
		int res = s.length();
 
		// longitud par o impar del string
		if (n % 2 == 0) {
			int[][] letters = new int[2][26];
 
			// llenamos la suma de sufijos
			for (int i = n - 1; i > -1; i--) { letters[i % 2][s.charAt(i) - 'a']++; }
 
			int even = 0, odd = 0;
 
			// hallamos la letra que más aparece en índices pares e impares
			for (int i = 0; i < 26; i++) {
				even = Math.max(even, letters[0][i]);
				odd = Math.max(odd, letters[1][i]);
			}
 
			res -= (even + odd);
		} else {
			int[][] pref = new int[2][26];
			int[][] suff = new int[2][26];
 
			// llenamos la suma de sufijos
			for (int i = n - 1; i > -1; i--) { suff[i % 2][s.charAt(i) - 'a']++; }
 
			// probamos índices a borrar
			for (int i = 0; i < s.length(); i++) {
				// el carácter ya no está en el sufijo
				suff[i % 2][s.charAt(i) - 'a']--;
 
				int even = 0, odd = 0;
 
				// hallamos la letra que más aparece en índices pares e impares
				for (int j = 0; j < 26; j++) {
					even = Math.max(even, suff[1][j] + pref[0][j]);
					odd = Math.max(odd, suff[0][j] + pref[1][j]);
				}
 
				res = Math.min(res, s.length() - even - odd);
 
				// el carácter ahora está en el prefijo
				// hay que agregarlo al final del bucle porque
				// si no se contaría cuando está "borrado"
				pref[i % 2][s.charAt(i) - 'a']++;
			}
		}
 
		return res;
	}
}


def solve():
	n = int(input())
	s = input()
 
	res = len(s)
 
	# longitud par o impar del string
	if n % 2 == 0:
		letters = [[0] * 26, [0] * 26]
 
		# llenamos la suma de sufijos
		for i in range(len(s)):
			letters[i % 2][ord(s[i]) - ord("a")] += 1
 
		best = [0, 0]
 
		# hallamos la letra que más aparece en índices pares e impares
		for i in range(2):
			best[i] = max(letters[i])
 
		res -= best[0] + best[1]
	else:
		pref = [[0] * 26, [0] * 26]
		suff = [[0] * 26, [0] * 26]
 
		# llenamos la suma de sufijos
		for i in range(len(s) - 1, -1, -1):
			suff[i % 2][ord(s[i]) - ord("a")] += 1
 
		# probamos índices a borrar
		for i in range(n):
			# el carácter ya no está en el sufijo
			suff[i % 2][ord(s[i]) - ord("a")] -= 1
 
			best = [0, 0]
 
			# hallamos la letra que más aparece en índices pares e impares
			for j in range(26):
				best[0] = max(best[0], suff[1][j] + pref[0][j])
				best[1] = max(best[1], suff[0][j] + pref[1][j])
 
			res = min(res, len(s) - best[0] - best[1])
 
			# el carácter ahora está en el prefijo
			# hay que agregarlo al final del bucle porque
			# si no se contaría cuando está "borrado"
			pref[i % 2][ord(s[i]) - ord("a")] += 1
 
	print(res)
 
 
t = int(input())
 
for _ in range(t):
	solve()