Skip to Content
CTRL K

ABBC or BACB

Editorial oficial (C++) 

Explicación

La observación un poco rara que hay que hacer aquí es que el proceso de reemplazo se puede pensar como que las B “se comen” las A y dejan C donde estaban.

Este proceso se ve más claro en el 5.º caso de ejemplo:

AAAAAAB
AAAAABC
AAAABCC
...
BCCCCCC

Como las B dejan C atrás cuando se comen una A, tienen que elegir una dirección y comprometerse con ella.

Con eso, solo necesitamos esta información:

  1. Cuántas “rachas” de A hay y sus tamaños
  2. Cuántas B hay adyacentes a una racha de A.

Nótese que, como el string inicial solo puede alternar entre A y B, puede haber como máximo una racha de A más que B disponibles.

Si este es el caso, tenemos que renunciar a la racha más pequeña de A que ocurra. Si no, podemos imprimir la suma de todas las rachas de A —es decir, el número total de A en el string.

Implementación

Complejidad temporal: O(∣s∣)\mathcal{O}(|s|)

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		std::string str;
		std::cin >> str;
		str += 'X';  // Añadimos una X por conveniencia en el bucle de abajo
 
		int b_amts = 0;
		vector<int> a_runs;
		int a_total = 0;
 
		char last = str[0];
		int run_len = 1;
		for (int i = 1; i < str.size(); i++) {
			if (str[i] != last) {
				if (last == 'A') {
					a_runs.push_back(run_len);
					a_total += run_len;
				} else if (last == 'B') {
					// Cualquier racha de B puede tener como máximo 2 adyacentes a A
					b_amts += std::min(run_len, 2);
				}
				run_len = 0;
			}
			last = str[i];
			run_len++;
		}
 
		// Aplicamos la fórmula descrita en la explicación de arriba
		if (b_amts < a_runs.size()) {
			int exclude = *std::min_element(a_runs.begin(), a_runs.end());
			cout << a_total - exclude << '\n';
		} else {
			cout << a_total << '\n';
		}
	}
}
import java.io.*;
import java.util.*;
 
public class ABBCorBACB {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			// Añadimos una X por conveniencia en el bucle de abajo
			String str = read.readLine() + 'X';
 
			int bAmts = 0;
			List<Integer> aRuns = new ArrayList<>();
			int aTotal = 0;
 
			char last = str.charAt(0);
			int runLen = 1;
			for (int i = 1; i < str.length(); i++) {
				if (str.charAt(i) != last) {
					if (last == 'A') {
						aRuns.add(runLen);
						aTotal += runLen;
					} else if (last == 'B') {
						// Cualquier racha de B puede tener como máximo 2 adyacentes a A
						bAmts += Math.min(runLen, 2);
					}
					runLen = 0;
				}
				last = str.charAt(i);
				runLen++;
			}
 
			// Aplicamos la fórmula descrita en la explicación de arriba
			if (bAmts < aRuns.size()) {
				System.out.println(aTotal - Collections.min(aRuns));
			} else {
				System.out.println(aTotal);
			}
		}
	}
}
from itertools import groupby
 
for _ in range(int(input())):
	string = input()
 
	b_amts = 0
	a_runs = []
	for char, amt in groupby(string):
		if char == "A":
			a_runs.append(len(list(amt)))
		else:
			# Cualquier racha de B puede tener como máximo 2 adyacentes a A
			b_amts += min(len(list(amt)), 2)
 
	# Aplicamos la fórmula descrita en la explicación de arriba
	if b_amts < len(a_runs):
		print(sum(a_runs) - min(a_runs))
	else:
		print(sum(a_runs))
Fundamentos