Skip to Content
CTRL K

Palindromes Coloring

Editorial oficial (C++) 

Explicación

Podemos resolver este problema de forma voraz formando primero pares palindrómicos a partir de caracteres idénticos.

Primero añadimos pares de caracteres idénticos a cada color, intentando mantenerlo todo lo más parejo posible. Cuando no queden más pares, todavía podemos añadir un carácter más al medio de cada palíndromo.

Nótese que al añadir caracteres sueltos, puede ser óptimo romper algunos pares para equilibrar un poco más las cosas. Por eso añadimos 2 * (num_pairs % k) cerca del final.

Implementación

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

#include <array>
#include <iostream>
#include <string>
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, k;
		std::string string;
		std::cin >> n >> k >> string;
 
		std::array<int, 26> char_freq{0};
		for (char x : string) { char_freq[x - 'a']++; }
 
		int num_pairs = 0;
		int num_odd = 0;
		for (int i = 0; i < 26; i++) {
			num_pairs += char_freq[i] / 2;
			num_odd += (char_freq[i] % 2 == 1);
		}
 
		int res = 2 * (num_pairs / k);
		num_odd += 2 * (num_pairs % k);
 
		res += (num_odd >= k);
		std::cout << res << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class PalindromeColoring {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
			int k = io.nextInt();
			String string = io.next();
 
			int[] charFreq = new int[26];
			for (int i = 0; i < n; i++) { charFreq[string.charAt(i) - 'a'] += 1; }
 
			int numPairs = 0;
			int numOdd = 0;
			for (int i = 0; i < 26; i++) {
				numPairs += charFreq[i] / 2;
				numOdd += charFreq[i] % 2;
			}
 
			int res = 2 * (numPairs / k);
			numOdd += 2 * (numPairs % k);
 
			res += numOdd >= k ? 1 : 0;
			io.println(res);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
from collections import Counter
 
for _ in range(int(input())):
	n, k = map(int, input().split())
	char_freq = Counter(input())
 
	num_pairs = 0
	num_odd = 0
	for c in char_freq.values():
		num_pairs += c // 2
		num_odd += c % 2
 
	res = 2 * (num_pairs // k)
	num_odd += 2 * (num_pairs % k)
 
	res += num_odd >= k
	print(res)
Fundamentos